Pagini recente » Cod sursa (job #811184) | Cod sursa (job #2113214) | Cod sursa (job #1513439) | Cod sursa (job #1285051) | Cod sursa (job #2445892)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMAX = 2e6 + 5;
char A[2 * NMAX], B[NMAX];
int N, M, T, auxN, phi[2 * NMAX], ans;
vector < int > Sol;
int main()
{
f.tie(NULL);
f >> A >> B;
N = (int)strlen(A);
auxN = N;
M = (int)strlen(B);
strcat(A, "#");
strcat(A, B);
T = (int)strlen(A);
ans = 0;
for(int i = 1; i < T; ++i)
{
while(ans && A[i] != A[ans])
ans = phi[ans - 1];
if(A[i] == A[ans])
++ans;
phi[i] = ans;
}
for(int i = auxN + 1; i < T; ++i)
if(phi[i] == auxN)
Sol.push_back(i - 2 * auxN);
g << (int)Sol.size() << '\n';
for(int i = 0; i < min(1000, (int)Sol.size()); ++i)
g << Sol[i] << ' ';
g << '\n';
return 0;
}