Cod sursa(job #1330633)

Utilizator rsteliRadu Stelian rsteli Data 30 ianuarie 2015 20:29:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

const int nmax=2000010;

int n,m,p[nmax],t,v[1010],nr;
char a[nmax],b[nmax];

int main()
{
    int i,j;
    cin.get(a+1,nmax);
    cin.get();
    cin.get(b+1,nmax);
    n=strlen(a+1);
    m=strlen(b+1);
    for (i=2;i<=n;i++)
    {
        while (t && a[t+1]!=a[i])
            t=p[t];
        if (a[t+1]==a[i])
            t++;
        p[i]=t;
    }
    t=0;
    for (i=1;i<=m;i++)
    {
        while (t && a[t+1]!=b[i])
            t=p[t];
        if (a[t+1]==b[i])
            t++;
        if (t==n)
        {
            t=p[n];
            if (v[0]<1000)
                v[++v[0]]=i-n;
            nr++;
        }
    }
    cout<<nr<<'\n';
    for (i=1;i<=v[0];i++)
        cout<<v[i]<<" ";
}