Cod sursa(job #952074)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 22 mai 2013 17:50:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
// KMP

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int NMAX = 2000005;
int Pi[NMAX],i,N,M,Cnt;
char A[NMAX],B[NMAX];
vector<int> Sol;
vector<int>::iterator it;
void Prefix()
{
    Pi[1]=0; int q=0;
    for(i=2;i<=N;i++)
    {
        while(q && A[q+1]!=A[i]) q=Pi[q];
        if(A[q+1]==A[i]) q++;
        Pi[i]=q;
    }
}
void KMP()
{
    int q=0;
    for(i=1;i<=M;i++)
    {
        while(q && A[q+1]!=B[i]) q=Pi[q];
        if(A[q+1]==B[i]) q++;
        if(q==N)
        {
            Cnt++;
            if(Cnt<=1000) Sol.push_back(i-N);
        }
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",A+1,B+1);
    N=strlen(A+1); M=strlen(B+1);
    Prefix(); KMP();
    printf("%d\n",Cnt);
    for(it=Sol.begin();it!=Sol.end();it++) printf("%d ",*it);
    return 0;
}