Pagini recente » Cod sursa (job #1032524) | Cod sursa (job #2633327) | Cod sursa (job #1515912) | Cod sursa (job #2784152) | Cod sursa (job #2443726)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("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()
{
fin >> 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;
}
}
fout << K << '\n';
K = min(K, 1000);
for(int i = 1; i <= K; i++)
fout << Sol[i] - N << " ";
fin.close();
fout.close();
return 0;
}