Cod sursa(job #614876)

Utilizator The_DisturbedBungiu Alexandru The_Disturbed Data 7 octombrie 2011 20:29:23
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <string.h>
using namespace std;
char s[2000000],a[2000000];
int p[2000000],i,j,m,n,k,sol[1002],ns;
int main()
{
    ifstream f("in.txt");
    ofstream g("out.txt");
    f>>(a+1)>>(s+1);
    n=strlen(a+1);
    m=strlen(s+1);
    for(i=2;i<=n;i++)
    {
        k=p[i-1]+1;
        if( a[k] != a[i] ) k=p[k]+1;
        if( a[k] == a[i] ) p[i]=k;
        else p[i]=0;
    }
    k=0;
    ns=0;
    for(i=1;i<=m+1;i++)
    {
        while( k>0 && s[i] != a[k+1] ) k=p[k];
        if( a[k+1] == s[i] ) ++k;
        if( k == n )
        {
            if(ns<999)sol[ns++]=i-k;
            k=p[k];
        }
    }
    g<<ns<<"\n";
    for(i=0;i<ns;i++)g<<sol[i]<<" ";
    return 0;
}