Pagini recente » Cod sursa (job #1582037) | Cod sursa (job #1277502) | Cod sursa (job #1274068) | Cod sursa (job #712568) | Cod sursa (job #2001454)
#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 && 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){
while(j && small[j] != big[i])
j = table[j-1];
if(small[j] == big[i])
j++;
if(j == Ns){
j = table[j-1];
result.push_back(i - Ns + 1);
}
}
return result;
}
int main(){
cin.sync_with_stdio(false);
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){
printf("%d\n",result.size());
for(int i = 0; i < 1000; ++i)
printf("%d ",result[i]);
}else{
int Nres = result.size();
printf("%d\n",Nres);
for(int i = 0; i < Nres; ++i)
printf("%d ",result[i]);
}
return 0;
}