Cod sursa(job #1466440)

Utilizator Tester01tester Tester01 Data 29 iulie 2015 10:37:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>
using namespace std;
#define MaxSize 4000013

vector <int> KMP (string s){
	vector <int> pi(MaxSize,0);
	pi[0]=0;
	for (int i=1;i<s.size();++i){
		int k = pi[i-1];
		while(s[i]!=s[k] && k>0) k = pi[k-1];
		if (s[i]==s[k]) ++k;
		pi[i]=k;
	}
	return pi; 
}

string a ,b;
int sol[1013];

int main(void) {
 ifstream cin("strmatch.in");
 ofstream cout("strmatch.out");
 cin>>a>>b;
 int size = a.size();
 a+='$'+b;
 vector <int> Match = KMP(a); 
 for (int i=size+1;i<Match.size();++i)
   if (Match[i]==size) {
   	 ++sol[0];
     if (sol[0]<=1000) sol[sol[0]]=i-2*size;
   }
 cout<<sol[0]<<"\n";
 for (int i=1;i<=min(1000,sol[0]);++i) 
   cout<<sol[i]<<" ";
 return 0;
}