Pagini recente » Cod sursa (job #2534900) | Cod sursa (job #1580229) | Cod sursa (job #2165426) | Cod sursa (job #2196609) | Cod sursa (job #2238926)
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s, t;
vector <int> sol;
int q, n, m, i, pr[NMAX], cnt;
int main(){
f >> s >> t;
n = s.size();
m = t.size();
s = '#' + s;
t = '#'+ t;
for(i = 2; i <= n; i++){
while(q && s[i] != s[q+1]){
q = pr[q];
}
if(s[i] == s[q+1]){
q++;
}
pr[i] = q;
}
q = 0;
for(i = 1; i <= m; i++){
while(q && t[i] != s[q + 1]){
q = pr[q];
}
if(t[i] == s[q + 1]){
q++;
}
if(q == n){
q = pr[q];
if(cnt < 1000){
sol.push_back(i - n);
}
cnt++;
}
}
g<< cnt << '\n';
for(auto it : sol){
g << it << ' ';
}
return 0;
}