Cod sursa(job #2106236)

Utilizator andreicontorandrei contor andreicontor Data 15 ianuarie 2018 15:13:51
Problema Prefix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
//KMP
#include<cstring>
#include<cstdio>
using namespace std;
int i,k,urmator[1001];
char p[101],t[1001];
void prefix()
{
    k=0;
    urmator[1]=0;
    for(i=2;i<=strlen(p);i++)
    {
        while(k>0&&p[i]!=p[k+1])
            k=urmator[k];
        if(p[i]==p[k+1])
            k++;
        urmator[i]=k;
    }
}
int main()
{
    freopen("p.in","r",stdin);
    freopen("p.out","w",stdout);
    gets(t+1);
    t[0]='*';
    gets(p+1);
    p[0]='*';
    prefix();
    k=0;
    for(i=2;i<=strlen(t);i++)
    {
        while(k>0&&p[k+1]!=t[i])
            k=urmator[k];
        if(p[k+1]==t[i])
            k++;
        if(k==strlen(p)-1)
        {
            printf("%d\n",i-strlen(p)+2);
            k=urmator[k];
        }
    }
    return 0;
}