Cod sursa(job #972492)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 11 iulie 2013 20:14:13
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#define NMax 2000005
#include <fstream>
#include<cstring>
#include<algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[NMax],B[NMax];int N,M,P[NMax],Nr,Sol[1002];
void Read()
{
    fin>>(A+1)>>(B+1);
    fout<<(A+1)<<'\n'<<(B+1);
    M=strlen(A+1);
    N=strlen(B+1);
}
void Build_Prefixes()
{
    int i,q;
    P[1]=0;
    for(q=0,i=2;i<=M;i++)
    {
        while(q&&A[q+1]!=A[i])
            q=P[q];
        if(A[q+1]==A[i])
            q++;
        P[i]=q;
    }
}
void KMP()
{
    int i,q=0;
    for(i=1;i<=N;i++)
    {
        while(q&&A[q+1]!=B[i])
            q=P[q];
        if(A[q+1]==B[i])
            q++;
        if(q==M)
        {
            Nr++;
            if(Nr<=1000)
                Sol[Nr]=i-M;
        }
    }
}
void Print()
{
    int i;
    fout<<Nr<<"\n";
    for(i=1;i<=min(Nr,1000);i++)
        fout<<Sol[i]<<" ";
    fout<<"\n";
}
int main()
{
    Read();
    Build_Prefixes();
    KMP();
    Print();
    return 0;
}