Pagini recente » Cod sursa (job #1995930) | Cod sursa (job #1155867) | Cod sursa (job #42407) | Cod sursa (job #1105914) | Cod sursa (job #2565843)
#include <bits/stdc++.h>
#define MAXN 2000005
#define FILENAME std::string("strmatch")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");
int N, M;
char A[MAXN], B[MAXN];
int count;
std::vector <int> sol;
void addToSol(int idx) {
++ count;
if (sol.size() < 1000) sol.push_back(idx);
}
int LPS[MAXN];
void computeLPS(char S[], int N) {
int len = 0;
for (int i=1; i<=N; ++i) {
while (len != 0 && S[len+1] != S[i])
len = LPS[len];
LPS[i] = len;
if (S[len+1] == S[i]) ++ len;
}
}
void KMP() {
computeLPS(A, N);
int len = 0;
for (int i=1; i<=M; ++i) {
while (len != 0 && A[len+1] != B[i])
len = LPS[len];
if (A[len+1] == B[i]) ++ len;
if (len == N) addToSol(i-len);
}
}
int main()
{
input >> (A+1) >> (B+1);
N = strlen(A+1);
M = strlen(B+1);
KMP();
output << count << '\n';
for (auto &it:sol) output << it << ' ';
return 0;
}