Pagini recente » Cod sursa (job #1211047) | Cod sursa (job #293451) | Cod sursa (job #2843948) | Cod sursa (job #383707) | Cod sursa (job #2191719)
#include <bits/stdc++.h>
using namespace std;
const int LIM = 1e3;
const int MAXN = 2e6;
char s[MAXN + 2], t[MAXN + 2];
int pi[MAXN + 1];
vector < int > sol;
int main()
{
ifstream fin("strmatch.in");
fin >> (s + 1) >> (t + 1);
fin.close();
int k = 0, ans = 0, n;
for (int i = 2; s[i] != 0; ++i, n = i) {
for (k = k; k > 0 && s[k + 1] != s[i]; k = pi[k]) {}
pi[i] = (k += (s[k + 1] == s[i]));
}
k = 0;
for (int i = 1; t[i] != 0; ++i) {
for (k = k; k > 0 && s[k + 1] != t[i]; k = pi[k]) {}
if ((k += (s[k + 1] == t[i])) == n - 1) {
++ans;
if (sol.size() < LIM)
sol.push_back(i - n + 1);
}
}
ofstream fout("strmatch.out");
fout << ans << '\n';
for (auto it : sol)
fout << it << " ";
fout.close();
return 0;
}