Cod sursa(job #1323457)

Utilizator LycrsTrifan Tamara Lycrs Data 21 ianuarie 2015 01:05:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb

#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

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

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

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

        prefix[j]=a;
    }
}

void solve()
{

    int a=0;
    for (int i = 1; i <= n; ++i)
	{
		while (a && p[a+1] != s[i])
			a = prefix[a];
		if (p[a+1] == s[i])
			++a;
		if (a == m)
		{
			a = prefix[m];
			if (f < 1000)
				c[f] = i-m;
			f++;
		}
	}
}

void afisare()
{
    int u1=0, u2=0;
    cout<<f<<'\n';
    if (f<1000) u1=1;
        else u2=1;
    for(i=0; i< (f*u1 + 1000*u2) ; ++i)
        cout<<c[i]<<' '; cout<<'\n';
}

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

    m = strlen (p+1) ;
    n = strlen (s+1) ;


    if (m>n)
        cout<<"0"<<"\n";
        else
        {
            MakePrefix();
            solve();
            afisare();
        }

    return 0;
}