Cod sursa(job #614880)

Utilizator The_DisturbedBungiu Alexandru The_Disturbed Data 7 octombrie 2011 20:34:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <string.h>
inline int min(int a, int b)
{
    return (a<b?a:b);
}
using namespace std;
char s[2000000],a[2000000];
int p[2000000],i,j,m,n,k,sol[1002],ns;
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    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;
            ns++;
            k=p[k];
        }
    }
    g<<ns<<"\n";
    for(i=0;i<min(1000,ns);i++) g<<sol[i]<<" ";
    return 0;
}