Pagini recente » Cod sursa (job #1122218) | Cod sursa (job #1103768) | Cod sursa (job #995899) | Cod sursa (job #3126440) | Cod sursa (job #1518527)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2000000 + 2;
char A[MAX_N], B[MAX_N];
int pi[MAX_N];
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> (A + 1) >> (B + 1);
int N = strlen(A + 1);
int M = strlen(B + 1);
int k = 0;
pi[1] = 0;
for (int i = 2; i <= N; ++i)
{
while (k > 0 && A[i] != A[k + 1])
k = pi[k];
if (A[i] == A[k + 1])
k++;
pi[i] = k;
}
vector<int> solutions;
k = 0;
for (int i = 1; i <= M; ++i)
{
while (k > 0 && B[i] != A[k + 1])
k = pi[k];
if (B[i] == A[k + 1])
k++;
if (k == N)
{
solutions.push_back(i - N);
k = pi[k];
}
}
out << solutions.size() << "\n";
for (int i = 0; i < min(1000, (int)solutions.size()); ++i)
out << solutions[i] << ' ';
in.close();
out.close();
return 0;
}