Pagini recente » Cod sursa (job #2615920) | Cod sursa (job #1590379) | Cod sursa (job #1212694) | Cod sursa (job #1800315) | Cod sursa (job #785703)
Cod sursa(job #785703)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MaxN = 2000005;
int N, M, Z[MaxN], Match[MaxN];
vector<int> MatchPos;
char Pattern[MaxN], String[MaxN];
void BuildZ() {
Z[1] = 0;
int Pos = 1, Right = 1;
for (int i = 2; i <= M; ++i) {
if (i <= Right)
Z[i] = min(Right-i+1, Z[i-Pos+1]);
for (; i+Z[i] <= M && Pattern[Z[i]+1] == Pattern[i+Z[i]]; ++Z[i]);
if (i+Z[i]-1 > Right)
Pos = i, Right = i+Z[i]-1;
}
}
void PatternMatch() {
int Pos = 0, Right = 0;
for (int i = 1; i <= N; ++i) {
if (i <= Right)
Match[i] = min(Right-i+1, Z[i-Pos+1]);
for (; Match[i] < M && i+Match[i] <= N && Pattern[Match[i]+1] == String[i+Match[i]]; ++Match[i]);
if (i+Match[i]-1 > Right)
Pos = i, Right = i+Match[i]-1;
if (Match[i] == M)
MatchPos.push_back(i-1);
}
}
void Solve() {
BuildZ();
PatternMatch();
}
void Read() {
freopen("strmatch.in", "r", stdin);
scanf("%s\n%s", Pattern+1, String+1);
M = strlen(Pattern+1), N = strlen(String+1);
}
void Print() {
freopen("strmatch.out", "w", stdout);
printf("%d\n", MatchPos.size());
for (int i = 0; i < 1000 && i < MatchPos.size(); ++i)
printf("%d ", MatchPos[i]);
printf("\n");
}
int main() {
Read();
Solve();
Print();
return 0;
}