Cod sursa(job #1892803)

Utilizator heracleRadu Muntean heracle Data 25 februarie 2017 11:58:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <cstring>

using namespace std;

const int Q=2000008;

char v[Q],s[Q];
int d[Q],rez[Q];

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	gets(v+1);
	//cin>>v+1;

	int size_v=strlen(v+1);
	
	for(int i=2; i<=size_v; i++)
	{
		int l=d[i-1];
		while(l && v[i]!=v[l+1])
			l=d[l];
		if(v[i]==v[l+1])
			l++;
		d[i]=l;
	}

/*
d[i] este lungimea maxima a doua 
subsecvente identice, una care incepe 
la pozitia 1 din v si alta 
care se termina la pozitia i din v
*/

//continuare

	gets(s+1);
	//cin>>s+1;

	int size_s=strlen(s+1);
	int t=0;
	int contor=0;
	for(int p=1; p<=size_s; p++)
	{
		while(t && v[t+1]!=s[p])
			t=d[t];
		if(v[t+1]==s[p])
			t++;
		if(t==size_v)
		{
			contor++;
			if(contor<=1000)
				rez[contor]=p-size_v;
			t=d[t];
		}
	}

	cout<<contor<<"\n";

	for(int i=1; i<=contor; i++)
		cout<<rez[i]<<" ";

}