Cod sursa(job #1295681)

Utilizator LycrsTrifan Tamara Lycrs Data 19 decembrie 2014 23:40:53
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <string>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

int n, i, m, j, prefix[2000005], a, k, f=0, c[1005];
string s, p, pp;

int main()
{
    cin>>p;
    cin>>s;

    m=p.size();
    n=s.size();

    p='%'+p;
    s='%'+s;

    a=0;
    prefix[1]=0;
    for(j=2; j<=m; ++j)
    {
        while(a>0 && p[a+1]!=p[j]) a=prefix[a];

        if (p[a+1]==p[j]) ++a;

        prefix[j]=a;
    }


    i=1; k=1; j=1;

    while ( n-k >= m-1 )
    {

        while (j<=m && s[i]==p[j])
        {
            ++i;
            ++j;
        }

        if (j>m)
        {

            ++f;
            c[f]=k-1;
            k=i;
            if (prefix[j-1]>0) k=i-prefix[j-1];
            if (f==1000) n=0;

        }
        else
        {
            if (i==k) ++i;
            k=i;

        }
        if (j>1) j=prefix[j-1]+1;

    }

 cout<<f<<'\n';
    for (i=1; i<=f; ++i)
        cout<<c[i]<<' ';


    return 0;
}