Pagini recente » Cod sursa (job #1466605) | Cod sursa (job #2988380) | Cod sursa (job #1827404) | Cod sursa (job #915924) | Cod sursa (job #2376194)
#include <bits/stdc++.h>
#define ANS_COUNT 1000
#define MAXN 2000005
int N, M;
char A[MAXN], B[MAXN];
int LPS[MAXN];
void ComputeLPS() {
int Len = 0;
for (int i=2; i<=N; ++i) {
while (Len && A[i] != A[Len+1])
Len = LPS[Len];
if (A[i] == A[Len+1])
++ Len;
LPS[i] = Len;
}
}
std::vector <int> Ans;
int Count;
void KMP() {
ComputeLPS();
for (int i=1, j=0; i<=M; ++i) {
while (j && B[i] != A[j+1])
j = LPS[j];
if (B[i] == A[j+1])
++ j;
if (j == N) {
if (Count < ANS_COUNT)
++ Count, Ans.push_back(i-N);
else
++ Count;
}
}
}
std::ifstream In ("strmatch.in");
std::ofstream Out("strmatch.out");
void Citire() {
In >> (A+1) >> (B+1);
N = strlen(A+1);
M = strlen(B+1);
}
void Rezolvare() {
KMP();
Out << Count << '\n';
for (auto idx:Ans)
Out << idx << ' ';
}
int main()
{
Citire();
Rezolvare();
return 0;
}