Pagini recente » Cod sursa (job #774912) | Cod sursa (job #1546730) | Cod sursa (job #2604795) | Cod sursa (job #2823598) | Cod sursa (job #2877454)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int nmax = 2e6 + 5;
int lps[nmax];
string pat, txt;
vector <int> ans;
void preprocess(int n) {
int i = 0, j = 1;
while (j < n) {
if (pat[i] == pat[j]) {
lps[j] = i + 1;
++j;
++i;
}
else {
i = lps[i - 1];
if (i == 0)
lps[j] = 0, ++j;
}
}
}
int main()
{
fin >> pat;
fin >> txt;
int n = pat.size();
int m = txt.size();
preprocess(n);
int i = 0, j = 0, k = 0;
while (i < m) {
if (txt[i] == pat[j])
++i, ++j;
else {
if (j == 0)
++i;
else {
j = lps[j - 1];
if (j == 0)
++i;
}
}
if (j == n) {
ans.push_back(i - j);
j = lps[j - 1];
++k;
}
}
fout << k << '\n';
for (int i : ans)
fout << i << ' ';
return 0;
}