Cod sursa(job #2307842)

Utilizator adriashkin.07alehandru69 adriashkin.07 Data 25 decembrie 2018 19:07:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fs first
#define sc second

int n,m,p[2000005],k,t,a[1005];   
string S,s;

int main()
{
	ifstream cin("strmatch.in");
	ofstream cout("strmatch.out");
	cin>>s;
	cin>>S;
	s=" "+s;
	S=" "+S;
	n=s.size();
	m=S.size();
	k=0;
	for(int i=2;i<=n;i++)
	{
		while(k>0 && s[k+1]!=s[i]) k=p[k];
		if(s[k+1]==s[i])k++;
		p[i]=k;
	}
	k=0;
	for(int i=1;i<=m;i++)
	{
		while(k>0 && s[k+1]!=S[i]) k=p[k];
		if(s[k+1]==S[i])k++;
		if(k==n-1)  a[t++]=i-n+1;
	}
	cout<<t<<"\n";
	t=min(t,1000);
	for(int i=0;i<t;i++)
		cout<<a[i]<<" ";


}