Pagini recente » Cod sursa (job #3030653) | Cod sursa (job #440792) | Cod sursa (job #2641846) | Cod sursa (job #483244) | Cod sursa (job #2868336)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN = 2e6 + 5;
string text, pattern;
vector<int> ans;
int pi[MAXN];
int main() {
fin >> pattern >> text;
int n = (int) text.length();
int m = (int) pattern.length();
text = '$' + text;
pattern = '$' + pattern;
for(int i = 2, q = 0; i <= m; i++) {
while(q && pattern[q + 1] != pattern[i])
q = pi[q];
if(pattern[q + 1] == pattern[i])
q++;
pi[i] = q;
}
for(int i = 1, q = 0; i <= n; i++) {
while(q && pattern[q + 1] != text[i])
q = pi[q];
if(pattern[q + 1] == text[i])
q++;
if(q == m) {
q = pi[q];
if((int) ans.size() < 1000)
ans.push_back(i - m);
}
}
fout << (int) ans.size() << '\n';
for(int id : ans)
fout << id << ' ';
fout << '\n';
return 0;
}