Cod sursa(job #645144)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 8 decembrie 2011 18:17:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <cstring>
using namespace std;

int N,M,pr[2000100],sol,v[2000100];
char A[2000100],B[2000100];

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    f>>(A+1)>>(B+1);
    N=strlen(A+1);M=strlen(B+1);

    for(int i=2,k=0;i<=N;++i)
    {
        while(k>0 && A[k+1]!=A[i]) k=pr[k];
        if(A[k+1]==A[i]) ++k;
        pr[i]=k;
    }

    for(int i=1,k=0;i<=M;++i)
    {
        while(k>0 && A[k+1]!=B[i]) k=pr[k];
        if(A[k+1]==B[i]) ++k;
        if(k==N)
            v[++sol]=i-k,k=pr[k];
    }

    g<<sol<<'\n';
    for(int i=1;i<=sol;++i) g<<v[i]<<' ';
    g.close();
    return 0;
}