Cod sursa(job #793543)

Utilizator ucnahHancu Andrei ucnah Data 3 octombrie 2012 14:58:32
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>
#include <cstring>
#define N 2000010
using namespace std;
char a[N],b[N];
int urm[N],h[N],z;
void formare(char p[N])
{
    int m=strlen(p+1);
    urm[1]=0;
    int k=0;
    m--;
    for(int q=2;q<=m;q++)
    {
        while(k>0 && p[k+1]!=p[q])
            k=urm[k];
        if(p[k+1]==p[q])
            k++;
        urm[q]=k;
    }
}
void rezolvare(char p[N],char t[N])
{
    int n=strlen(t+1);
    int m=strlen(p+1);
    n--;
    m--;
    int q=0;
    for(int i=1;i<=n;i++)
    {
        while(q>0 && p[q+1]!=t[i])
            q=urm[q];
        if(p[q+1]==t[i])
            q++;
        if(q==m)
        {
            h[z++]=i-m+1;
            q=urm[q];
        }
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(a+1,N,stdin);
    fgets(b+1,N,stdin);
    formare(a);
    rezolvare(a,b);
    printf("%d\n",z);
    for(int i=0;i<z;i++)
        printf("%d ",h[i]);
    return 0;
}