Cod sursa(job #1486684)

Utilizator afkidStancioiu Nicu Razvan afkid Data 15 septembrie 2015 13:02:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 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 n=x.length()-1;
	int k=0;
	kmpNext[0]=0;
	for(int i=2;i<=n;++i)
	{
		while(k>0 && x[i]!=x[k+1])
			k=kmpNext[k];
		if(x[i]==x[k+1])
			k++;
		kmpNext[i]=k;
	}
}

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

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