Pagini recente » Cod sursa (job #140002) | Cod sursa (job #2500269) | Cod sursa (job #2970975) | Cod sursa (job #1592602) | Cod sursa (job #2444314)
#include <cstring>
#include <fstream>
using namespace std;
ifstream i("strmatch.in");
ofstream o("strmatch.out");
const int LMax = 2e6;
int N, M, K, Sol[1005], Match[LMax + 5];
char A[LMax + 5], B[LMax + 5];
void Make_Prefix()
{
int q = 0;
for(int i = 2; i <= N; i++)
{
while(q && A[q + 1] != A[i])
q = Match[q];
if(A[q + 1] == A[i])
q++;
Match[i] = q;
}
}
int main()
{
i >> A + 1 >> B + 1;
N = strlen(A + 1);
M = strlen(B + 1);
Make_Prefix();
int q = 0;
for(int i = 1; i <= M; i++)
{
while(q && A[q + 1] != B[i])
q = Match[q];
if(A[q + 1] == B[i])
q++;
if(q == N)
{
q = Match[q];///nu exista A[N + 1]
if(++K <= 1000)
Sol[K] = i;
}
}
o << K << '\n';
K = min(K, 1000);
for(int i = 1; i <= K; i++)
o << Sol[i] - N << " ";
return 0;
}