Cod sursa(job #1169041)

Utilizator BogdanOuatuOuatu Bogdan-Ioan BogdanOuatu Data 10 aprilie 2014 12:23:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
//#include <iostream>
#include <fstream>
#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()
{
    int i,q,so=0;
    fin>>(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';
    for(i=1;i<=so;i++)
        fout<<s[i]<<' ';
    fout<<'\n';
    fin.close();
    fout.close();
    return 0;
}