Pagini recente » Cod sursa (job #881766) | Cod sursa (job #547251) | Cod sursa (job #1790477) | Cod sursa (job #761623) | Cod sursa (job #2375752)
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int Nmax = 2000005;
char A[Nmax], B[Nmax];
int main()
{
int w = 0, A_size, B_size;
in.get(A, Nmax);
in.get();
in.get(B, Nmax);
A_size = strlen(A);
B_size = strlen(B);
vector<int> sol;
vector<int> pi(A_size + 1);
for (int i = A_size; i >= 1; i--)
A[i] = A[i - 1];
for (int i = B_size; i >= 1; i--)
B[i] = B[i - 1];
for (int i = 2; i <= A_size; i++)
{
while (w != 0 && A[w + 1] != A[i])
w = pi[w];
if (A[w + 1] == A[i])
w++;
pi[i] = w;
}
w = 0;
for (int i = 1; i <= B_size; i++)
{
while (w != 0 && A[w + 1] != B[i])
w = pi[w];
if (A[w + 1] == B[i])
w++;
if (w == A_size)
{
sol.push_back(i - A_size);
w = pi[w];
}
}
int Size = sol.size();
out << Size << '\n';
for (int i = 0; i < min(Size, 1000); i++)
out << sol[i] << ' ';
return 0;
}