Pagini recente » Cod sursa (job #3139088) | Cod sursa (job #1994701) | Cod sursa (job #1674756) | Cod sursa (job #1911343) | Cod sursa (job #3286505)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN = 2000005;
string pat, str;
int lsp[MAXN];
vector<int> sol;
void precompute_lsp() {
int m = pat.size();
lsp[0] = 0;
int len = 0;
for (int i = 1; i < m; i++) {
while (len > 0 && pat[i] != pat[len]) {
len = lsp[len - 1]; // Backtrack
}
if (pat[i] == pat[len]) {
len++;
}
lsp[i] = len;
}
}
void kmp() {
int n = str.size(), m = pat.size();
int j = 0; // Index for pat
for (int i = 0; i < n; i++) {
while (j > 0 && str[i] != pat[j]) {
j = lsp[j - 1]; // Backtrack
}
if (str[i] == pat[j]) {
j++;
}
if (j == m) { // Found a match
if (sol.size() < 1000) sol.push_back(i - m + 1);
j = lsp[j - 1]; // Continue searching
}
}
}
int main() {
fin >> pat >> str;
precompute_lsp();
kmp();
fout << sol.size() << '\n';
for (int s : sol) fout << s << ' ';
return 0;
}