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