学步园

kmp算法，说实话理解起来真不容易，特别是自学。网上的讲解next有几种标志方法，虽然大概算法差不多，但是有点迷惑。想了几天，基本明白了，但是还是不太透彻。不能浪费太多时间在这里，以后回顾一下。kmp算法把复杂度O(nm)变成了O(n+m)，确实很不错，算法的魅力就在于此，妙不可言，吾等渣渣只能膜拜。我按照算法导论的方法，即next[1] = 0， 下标从1开始，网上有不错的代码http://blog.csdn.net/ederick/article/details/7242076。这个跟算法导论上的差不多

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    long n, m;
    int code[ 60001 ], next[ 60001 ], gate;
    long i, j, k;
    
    while ( cin >> n ) {
        for ( i = 1; i <= n; i++ )
            scanf( "%d", &code[ i ] );
            
        next[ 1 ] = 0;
        j = 0;
        for ( i = 2; i <= n; i++ )  
        {
            if(code[j+1]==code[i])
            j++;
            else j = 0;
            next[ i ] = j;
        }
        
        scanf( "%ld", &m );
        j = 0;
        for ( i = 1; i <= m; i++ ) 
        {
            scanf( "%d", &gate );
            if ( j != n ) 
            {
                if(code[j+1]==gate)
                j++;
            else j = next[ j ];
            if(j==n) k = i -j;
            }
        }           
        if(j == n) cout << k << endl;
        else cout << "no solution\n";
        
    }
    
    return 0;
    
}