Pagini recente » Cod sursa (job #875061) | Cod sursa (job #2752682) | Cod sursa (job #2808957) | Cod sursa (job #512543) | Cod sursa (job #2232740)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMax = 2000003;
string x,y;
int k;
int pi[NMax];
void KMP(string x, string y){
int k = -1;
pi[0] = -1;
for(int i = 1; i < x.size(); ++i){
while(k >= 0 && x[k + 1] != x[i])
k = pi[k];
if(x[k + 1] == x[i])
k++;
pi[i] = k;
}
int ans = 0;
k = -1;
vector<int> v;
for(int i = 1; i < y.size(); ++i){
while(k >= 0 && x[k + 1] != y[i])
k = pi[k];
if(x[k + 1] == y[i])
k++;
if(k == x.size() - 1){
ans++;
if(ans <= 1000){
v.push_back(i - x.size() + 1);
}
}
}
g << ans << '\n';
for(int i = 0; i < v.size(); ++i){
g << v[i] << ' ';
}
}
int main(){
f >> x;
f >> y;
KMP(x,y);
return 0;
}