【USACO 2.3.1】【洛谷P 470】最長プレフィックス【KMP】

タイトルの大意:
テーマリンク:
USACO:http://train.usaco.org/usacoprob2?a=dLE 0 hVDUyv 1&S=prefix洛谷:https://www.luogu.org/problemnew/show/P1470
複数のサブストリングと1つの文字列を与えて、この文字列の上位の何人が完全に掛け布団の列を覆うことができることを求めます.
考え方:
多くの人がD DPと検索を使うと言いますが、私はどう見てもK M P KMPです.O(n)O(n)O(n)O(n)の時間的複雑度において、S S Sシーケンスにおける要素の位置を求めることができ、プレフィックスとの考えを用いて、一つの配列で答えを記録し、一つの位置を見つけたら、頭の位置i iの答えa n s＿i＋ANs＿uを返します.i++ansi++で、尾の位置j jの答えa n s j+ans_j++ansj++です.すべての元素を一方的に変えながら操作して、時間複雑度O(n m)O(nm)O(nm)で、m m mは元素の個数を表します.そして、プレフィクスと、a n s ans ansの前のk個数が0より大きいなら、答えはk k kです.
コード:

#include 
#include 
#include 
using namespace std;

const int M=210;
const int N=200100;
int n,m,j,sum=1,next[20],ans[N];
char a[N],b[M][20],c[M];

int main()
{
    while (cin>>b[sum]+1&&b[sum][1]!='.') sum++;
    while (cin>>c)  //               
        for (int i=0;i<strlen(c);i++)
            a[++n]=c[i];
    for (int k=1;k<sum;k++)
    {
        memset(next,0,sizeof(next));
        m=strlen(b[k]+1);
        j=0;
        next[1]=0; 
        for (int i=1;i<m;i++)  // next
        {
            while (j&&b[k][j+1]!=b[k][i+1]) j=next[j];
            if (b[k][j+1]==b[k][i+1]) j++;
            next[i+1]=j;
        }
        j=0;
        for (int i=0;i<n;i++)  //KMP
        {
            while (j&&b[k][j+1]!=a[i+1]) j=next[j];
            if (b[k][j+1]==a[i+1]) j++;
            if (j==m)
            {
                ans[i+2]--;
                ans[i-m+2]++;
                j=next[j];
            }
        }
    }
    for (int i=1;i<=n;i++)
        ans[i]+=ans[i-1];  //      
    for (int i=1;i<=n;i++)
        if (ans[i]<=0)
        {
            printf("%d
",i-1);
            return 0;
        }
    printf("%d
",n);
    return 0;
}