Pagini recente » Cod sursa (job #324016) | Cod sursa (job #2167479) | Cod sursa (job #1391996) | Cod sursa (job #1860584) | Cod sursa (job #2976756)
#include <bits/stdc++.h>
#define MAXSZ 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, lps[MAXSZ];
char a[MAXSZ + 1], b[MAXSZ + 1];
void computeLPS() {
int length = 0;
lps[0] = 0;
for (int i = 1; i < n; i++) {
while (length > 0 && a[length] != a[i])
length = lps[length];
if (a[length] == a[i]) {
lps[i] = length++;
continue;
}
lps[i] = length;
}
}
vector<int> findMatches() {
vector<int> matches;
int j = 0;
for (int i = 0; i < m && matches.size() < 1000; i++) {
while (j > 0 && a[j + 1] != b[i])
j = lps[j];
if (a[j + 1] == b[i])
j++;
if (j == n - 1)
matches.push_back(i - n + 1);
}
return matches;
}
int main() {
fin.getline(a, MAXSZ);
fin.getline(b, MAXSZ);
n = (int) strlen(a);
m = (int) strlen(b);
computeLPS();
vector<int> matches = findMatches();
fout << matches.size() << '\n';
for (auto& match: matches)
fout << match << ' ';
return 0;
}