Cod sursa(job #1004637)

Utilizator dariusdariusMarian Darius dariusdarius Data 3 octombrie 2013 12:33:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
char A[2000005];
char B[2000005];
int pi[2000005];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int n,m;
    gets(A+1);n=strlen(A+1);
    gets(B+1);m=strlen(B+1);
    pi[1]=0;int k=0;
    for(int i=2;i<=n;i++)
    {
        while(k>0 && A[k+1]!=A[i])
            k=pi[k];
        if(A[k+1]==A[i]) k++;
        pi[i]=k;
    }
    vector<int> sol;
    k=0;
    for(int i=1;i<=m;i++)
    {
        while(k>0 && A[k+1]!=B[i])
            k=pi[k];
        if(A[k+1]==B[i])
            k++;
        if(k==n)
            sol.push_back(i-k);
    }
    printf("%d\n",(int)sol.size());
    for(int i=0;i<min(1000,(int)sol.size());i++)
        printf("%d%c",sol[i],i==min(1000,(int)sol.size())-1?'\n':' ');
    return 0;
}