Cod sursa(job #1486690)

Utilizator afkidStancioiu Nicu Razvan afkid Data 15 septembrie 2015 13:34:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 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];
int cnt;

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

void KMP(string p)
{
	int n=s.length();
	int m=p.length();
	cnt=0;
	preKmp(p);
	int k=0,i=0;
	while(i<n)
	{
		if(k==-1)
		{
			++i;
			k=0;
		}
		else if(p[k]==s[i])
		{
			++i;
			++k;
			if(k==m)
			{
				if(cnt<1000)
					match.push_back(i-m);
				++cnt;
				k=kmpNext[k];
			}
		}
		else
			k=kmpNext[k];
	}
}

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