算法应用（一）

1. 写一个函数使得在键盘输入的字符在输入"#"符号之后倒序输出输入的东西，如：输入：ABC#， 输出CBA.

void printReversl(){
    char a;
    scanf("%c", &a);
    if (a != '#')  printReversl();
    if (a != '#') printf("%c\n", a);
}

2. 手写字符匹配算法KMP。

// 用next数组装着元素回溯比较的下标
void getNext(String T, int *next){
    int j = 0;
    int i = 1;
    next[1] = 0;// 第一个元素的next默认就是0
    
    while (i < T[0]) {
        if (0 == j || T[i] == T[j]) {
            i++;
            j++;
           next[i] = j;
        }else{
            j = next[j];
        }
    }
}

// 返回值为匹配成功的位置，若匹配失败返回值=0.
int Index_KMP( String S, String T, int startPositon){
    int i = startPositon;// 从第startPositon开始在字符串S 中找子串T
    int j = 1;// 子串T中第一个元素是子串的长度，所以从第一个位置开始去匹配
    
    // 先生成T的next数组，next装着每个字符比较失败后回溯到下一个要比较的元素下标
    int next[10];
    getNext(T, next);
    
    while ( i <= S[0] && j <= T[0]) {
        if (S[i] == T[j]) {
            i++;
            j++;
        }else{
            if (0 == next[j]) {
                // 因为next[1]=0的，为0说明在最开头的位置跟现在的位置元素一样的，所以这个时候直接从下一个位置开始重新查找
                i++;
                j=1;
            }else{
                j = next[j];
            }
        }
    }
    
    if (j > T[0]) {
        return i - T[0];
    }
    return 0;
}

+ (void)test{
   char T[10] = " abcabaaa";
    char S[25] = " fdsafaaabcabaaadsafds";
    T[0] = 8;
    S[0] = 21;
    int position =  Index_KMP(S , T, 1);
    NSLog(@"在第 %d 个位置找到了", position);
}