Pagini recente » Cod sursa (job #2934925) | Cod sursa (job #2818235) | Cod sursa (job #1194011) | Cod sursa (job #327038) | Cod sursa (job #2456425)
#include <bits/stdc++.h>
using namespace std;
int pi[2000005];
string A, B;
int main() {
ios_base::sync_with_stdio(false);
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> A >> B;
A = " " + A;
B = " " + B;
int n = A.size() - 1;
int m = B.size() - 1;
pi[1] = 0;
for (int i = 2, k = 0; i <= n; ++i) {
while (A[i] != A[k + 1] && k != 0) k = pi[k];
if (A[i] == A[k + 1]) ++k;
pi[i] = k;
}
int nn = 0;
vector<int> sol;
for (int i = 0, j = 1; j <= m; ++j) {
while (A[i + 1] != B[j] && i != 0) i = pi[i];
if (A[i + 1] == B[j]) ++i;
if (i == n) {
if (sol.size() < 1000) sol.push_back(j - n);
nn++;
i = pi[i];
}
}
cout << nn << "\n";
for (auto i : sol) cout << i << " ";
cout << "\n";
return 0;
}