Pagini recente » Cod sursa (job #2281729) | Cod sursa (job #2110474) | Cod sursa (job #2796943) | Cod sursa (job #134755) | Cod sursa (job #1839100)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX = 2000006;
string s1, s2; int m, n;
int text[NMAX], pi[NMAX], pos[1010], k;
void KMP(){
pi[1] = 0;
int i = 0;
for(int j = 2; j <= m; j++){
while(i > 0 && s1[i+1] != s1[j]){
i = pi[i];
}
if(s1[i+1] == s1[j]) i++;
pi[j] = i;
}
}
int main(){
in >> s1 >> s2;
s1 = '|' + s1;
s2 = '|' + s2;
m = s1.size()-1;
n = s2.size()-1;
KMP();
int i = 0;
for(int j = 1; j <= n; j++){
while(i > 0 && s1[i+1] != s2[j]){
i = pi[i];
}
if(s1[i+1] == s2[j]) i++;
if(i == m){
if(k < 1000) pos[++k] = j-m;
i = pi[i];
}
}
out << k << '\n';
for(int j = 1; j <= k; j++) out << pos[j] << ' ';
return 0;
}