Pagini recente » Cod sursa (job #95247) | Cod sursa (job #2058341) | Cod sursa (job #1268992) | Profil dornescuvlad | Cod sursa (job #2261185)
#include <bits/stdc++.h>
#define MaxN 2000005
#define MaxA 1000
std::ifstream InFile("strmatch.in");
std::ofstream OutFile("strmatch.out");
char A[MaxN], B[MaxN];
int M, N, NAns,
LPS[MaxN];
std::vector <int> Ans;
void PrecomputeLPS() {
int Len = 0;
for (int i=2; i<=N; ++i) {
while (Len && A[i] != A[Len+1])
Len = LPS[Len];
if (A[Len+1] == A[i])
++Len;
LPS[i] = Len;
}
}
void KMP() {
PrecomputeLPS();
int Len = 0;
for (int i=1; i<=M; ++i) {
while(Len && B[i] != A[Len+1])
Len = LPS[Len];
if (A[Len+1] == B[i])
++Len;
if (Len == N) {
NAns ++;
if (NAns+1 <= MaxA)
Ans.push_back(i-N);
}
}
}
void Citire() {
InFile >> A+1 >> B+1;
N = strlen(A+1);
M = strlen(B+1);
}
void Rezolvare() {
KMP();
OutFile << NAns << '\n';
for (int i=0; i<NAns; ++i)
OutFile << Ans[i] << ' ' ;
}
int main()
{
Citire();
Rezolvare();
return 0;
}