Cod sursa(job #1169042)

Utilizator BogdanOuatuOuatu Bogdan-Ioan BogdanOuatu Data 10 aprilie 2014 12:27:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
//#include <iostream>
//#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;
//ifstream fin("strmatch.in");
//ofstream fout("strmatch.out");


char a[2000004],b[2000004];
int pi[2000004],s[2000004],n,m;
void Prefix()
{
    pi[1]=0;
    int i,k=0;
    for(i=2;i<=n;i++)
        {
            while((k>0)&&(a[k+1]!=a[i]))
                    k=pi[k];
            if(a[k+1]==a[i])
                k++;
            pi[i]=k;
        }
}
int main()
{
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    int i,q,so=0;
    scanf("%s%s", (a+1),(b+1));
    n=strlen(a+1);
    m=strlen(b+1);

    Prefix();
    q=0;
    for(i=1;i<=m;i++)
        {
            while((q>0)&&(a[q+1]!=b[i]))
                q=pi[q];
            if(a[q+1]==b[i])
                q++;
            if(q==n)
                s[++so]=i-n;
        }
//    fout<<so<<'\n';
    printf("%d\n",so);
    for(i=1;i<=so;i++)
        printf("%d ",s[i]);
//        fout<<s[i]<<' ';
//    fout<<'\n';
//    fin.close();
//    fout.close();
    return 0;
}