Pagini recente » Cod sursa (job #1375100) | Cod sursa (job #141612) | Cod sursa (job #243222) | Cod sursa (job #1105460) | Cod sursa (job #2375727)
#include <fstream>
#include <vector>
#include <cstring>
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)
{
if (sol.size() < 1000)
sol.push_back(i - A_size);
w = pi[w];
}
}
out << sol.size() << '\n';
for (int i = 0; i < sol.size(); i++)
out << sol[i] << ' ';
return 0;
}