Cod sursa(job #380839)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 7 ianuarie 2010 22:24:19
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<stdio.h>
#include<string.h>
#include<vector>

using namespace std;

#define nmax 2000002
#define mmax 2000002

int urm[mmax];
char t[nmax], p[mmax];
int d=0;

vector<int> v;


int n,m;

void urmator()
{
	int k=-1,x;
	urm[0]=0;
	for(x=1;x<m;x++)
	{
		while(k>0&&p[k+1]!=p[x])
			k=urm[k];
		if(p[k+1]==p[x])
			k++;
		urm[x]=k;
	}
}

int main()
{
	int i, x=-1;
	freopen("kmp.in", "r", stdin);
	freopen("kmp.out", "w", stdout);
	scanf("%s %s", &t, &p);
	n=strlen(t); m=strlen(p);
	urmator();
	for(i=0;i<n;i++)
	{
		while(x>0&&p[x+1]!=t[i])
			x=urm[x];
		if(p[x+1]==t[i])
			x++;
		if(x==m-1)
		{
			x=urm[x];
			d++;
			v.push_back(i);
		}
	}
	printf("%d\n", d);
	for(i=1;i<=d;i++)
		printf("%d ", v[i-1]);
	return 0;
}