学步园

//KMP算法的难度就在于next数组的求解和这个next数组与要匹配的主模式串有什么联系，搞明白了这个联系，
//再理解KMP算法就没有想象中的那么难了！网上的资料也有很多关于KMP算法的剖析，总的可以归纳为一句话：构造最大后缀长度数组！
//学什么都不可能一蹴而就的，需要经验的积累，时间的洗礼！ 
#include <iostream>
#include <string>
using namespace std;

int next[1000]; 
void get_next(string str, int *next)
{
     int i, j, len;
     len = str.length();
     next[0] = -1; 
     //下面的方法求出的next数组值较易让人接受，个人意见！ 
     for (i = 1; i < len; i++){
         j = next[i-1];
         while (j > -1 && str[i-1] != str[j])
                j = next[j];//如果不相等就进行j的回溯！ 
         next[i] = j + 1;//得出next数组的值 
     } 
     /* 
     //上面的做法也可以改为while形式的语句,只是while计算出的是最后一个失配时的j回溯值
    // （因为之前相等时的next数组值好似没有什么用处，当运用KMP时，只有再模式串不匹配时才回溯的，
    //好好理解这里，就知道这种方法与上面求出的next数组值不同的原因了！个人见解！呵呵！）！  
     i = 1; 
     j = 0;
     next[0] = -1;
     while (i < len){
           if (j == -1 || str[i] == str[j]){
                 i++;
                 j++; 
                 if (str[i] != str[j]) 
                     next[i] = j;
                 else
                     next[i] = next[j]; 
           } 
           else
                j = next[j]; 
     }
     */ 
     return ; 
} 

//与求next数组的值的方法相类似 ！ 
int kmp_findIndex(string str1, string str2)
{
    int i, j, len1, len2;
    len1 = str1.length();
    len2 = str2.length();
    get_next(str2, next);
    i = j = 0; 
    while (i < len1 && j < len2){
          if (j == -1 || str1[i] == str2[j]){
                i++;
                j++; 
          } 
          else
                j = next[j]; //不相等就进行j的回溯！（与上面第二种方法，我所说的相对应起来，就可以理解第二种next数组值了） 
    } 
    if (j >= len2)
        return i - len2;
    else
        return 0; 
} 


int main()
{
    int i; 
    string str1, str2;
    while (cin >> str1 >> str2){
          int ans = kmp_findIndex(str1, str2);
          cout << ans << endl; 
    } 
    
    system("pause"); 
}