Pagini recente » Cod sursa (job #1374628) | Rating Alexe Razvan (alexe.razvan) | Profil mondoteq | Cod sursa (job #751391) | Cod sursa (job #2001448)
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void makeTable(string s, vector<int> &table){
int counter = 0;
int N = s.size();
int j = 0;
for(int i = 1; i<N; ++i){
while(j>0 && s[j]!=s[i])
j = table[j-1];
if(s[j] == s[i])
++j;
table[i] = j;
}
}
vector<int> KMP(string small, string big, vector<int> table){
vector<int> result;
int Ns = small.size();
int Nb = big.size();
int j = 0;
for(int i = 0; i < Nb; ++i){
if(big[i] == small[j])
++j;
else if(j>0)
j = table[j-1];
if(j<0) j = 0;
if(j == Ns){
j = table[j-1];
result.push_back(i - Ns + 1);
}
}
return result;
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
string s1,s2;
//reading
cin>>s1;
cin>>s2;
vector<int> table(s1.size());
makeTable(s1,table);
vector<int> result = KMP(s1,s2,table);
if(result.size()>1000){
cout<<1000<<"\n";
for(int i = 0; i < 1000; ++i)
cout<<result[i]<<" ";
}else{
int Nres = result.size();
cout<<Nres<<endl;
for(int i = 0; i < Nres; ++i)
cout<<result[i]<<" ";
}
return 0;
}