Cod sursa(job #806637)

Utilizator UMihneaUngureanu Mihnea UMihnea Data 3 noiembrie 2012 10:58:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <cstring>
#define N 2000010
using namespace std;
char *c,a[N],b[N];
int n,m,i,q,p[N],cnt,sol[1001];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    c=a+1;
    scanf("%s",c);
    n=strlen(c);
    c=b+1;
    scanf("%s",c);
    m=strlen(c);
    for(i=2;i<=n;i++)
    {
        while(q>0&&a[i]!=a[q+1])
        q=p[q];
        if(a[i]==a[q+1])
        q++;
        p[i]=q;
    }
    q=0;
    for(i=1;i<=m;i++)
    {
        while(q>0&&b[i]!=a[q+1])
        q=p[q];
        if(b[i]==a[q+1])
        q++;
        if(q==n)
        {
            cnt++;
            if(cnt<=1000)sol[cnt]=i-n;
        }
    }
    printf("%d\n",cnt);
    if(cnt>1000)cnt=1000;
    for(i=1;i<=cnt;i++)
        printf("%d ",sol[i]);
    return 0;
}