Pagini recente » Cod sursa (job #2167969) | Cod sursa (job #3168403) | Cod sursa (job #581568) | Cod sursa (job #376530) | Cod sursa (job #966275)
Cod sursa(job #966275)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include <string>
#include <algorithm>
using namespace std;
ifstream ff("strmatch.in");
ofstream gg("strmatch.out");
string pp, ss;
int uu[2000001], w;
vector<int> vv;
void pfx(){
int k = 0, l = pp.length();
uu[1] = 0;
for(int i=2;i<l;i++){
while(k>0 && pp[k+1]!=pp[i])k=uu[k];
if(pp[k+1]==pp[i])k++;
uu[i]=k;
}
}
void kmp(){
int k = 0, l = ss.length(), n = pp.length();
for(int i=1;i<l;i++){
while(k>0 && pp[k+1]!=ss[i])k=uu[k];
if(pp[k+1]==ss[i])k++;
if(k==n-1){
w++;
if(w<=1000)vv.push_back(i-k);
k=uu[k];
}
}
}
int main(){
ff >> pp >> ss;
pp = " " + pp;
ss = " " + ss;
pfx();
kmp();
gg << w << "\n";
for(int i=0;i<vv.size();i++) gg << vv[i] << " ";
return 0;
}