Cod sursa(job #1486662)

Utilizator afkidStancioiu Nicu Razvan afkid Data 15 septembrie 2015 12:34:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define M 2000100

using namespace std;
inline int MAX(int a,int b){return (a>b)?a:b;}
inline int MIN(int a,int b){return (a<b)?a:b;}
int t,n;
string s,p;
vector<int> match;
int kmpNext[M];

void preKmp(string x)
{
	int i,j;
	i=0;
	j=kmpNext[0]=-1;
	while(i<x.length())
	{
		while(j>-1 && x[i]!=x[j])
			j=kmpNext[j];
		i++;
		j++;
		if(x[i]==x[j])
			kmpNext[i]=kmpNext[j];
		else
			kmpNext[i]=j;
	}
}

void KMP(string k)
{
	int i,j;
	preKmp(k);
	i=j=0;
	while(j<s.length())
	{
		while(i>-1 && k[i]!=s[j]) i=kmpNext[i];
		i++;
		j++;
		if(i==k.length())
		{
			if(match.size()<1000)
				match.push_back(j-i);
			i=kmpNext[i];
		}
	}
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>p>>s;
	KMP(p);
	cout<<match.size()<<"\n";
	for(int i=0;i<match.size();++i)
	{
		if(i)
			cout<<" "<<match[i];
		else
			cout<<match[i];
	}
	return 0;
}