Cod sursa(job #1168989)

Utilizator BogdanOuatuOuatu Bogdan-Ioan BogdanOuatu Data 10 aprilie 2014 01:12:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 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()
{
    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,j=0,so=0;
    fin>>a>>b;
    n=strlen(a);
    m=strlen(b);
    for (i=n;i;--i)
        a[i]=a[i-1];
    a[0] = ' ';
	for (i=m;i;--i)
        b[i] = b[i-1];
    b[0] = ' ';
    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[++j]=i-n,so++;
        }
    fout<<so<<'\n';
    for(i=1;i<=so;i++)
        fout<<s[i]<<' ';
    fout<<'\n';
    fin.close();
    fout.close();
    return 0;
}