Cod sursa(job #1387612)

Utilizator azkabancont-vechi azkaban Data 14 martie 2015 15:13:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <bits/stdc++.h>
using namespace std;
string s,s2;
int i,j,n,k,sol(0);
int pi[1000013];
vector <int> V;

void kmp()
{
 pi[0]=0;
 for (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;
   }
}

int main(void)
{
 ifstream cin("strmatch.in");
 ofstream cout("strmatch.out");
 getline(cin,s);
 getline(cin,s2);
 int length=s.size();
 s+='#'+s2;
 kmp();
 for (i=0;i<s.size();++i)	
   if (pi[i]==length) 
     V.push_back(i-2*length);
 cout<<V.size()<<"\n";
 for (i=0;i<V.size();++i)
   {
   	if (i>1000) break;
   	cout<<V[i]<<" ";
   }    
 return 0;
}