Pagini recente » Cod sursa (job #2623120) | Cod sursa (job #3134265) | Cod sursa (job #1397492) | Cod sursa (job #1252553) | Cod sursa (job #2924007)
#include <bits/stdc++.h>
using namespace std;
const string fisier = "strmatch";
ifstream fin (fisier + ".in");
ofstream fout (fisier + ".out");
const int NM = 2e6 + 5;
char s[NM], t[NM];
int n, m, a[NM];
vector<int>ans;
void precalc (char s[]){
int index = 0;
a[0] = 0;
for (int i = 1; i < n; i++){
if (s[i] == s[index]){
index += 1;
a[i] = index;
i += 1;
}
else{
if (index != 0){
index = a[index - 1];
}
else{
a[i] = 0;
i += 1;
}
}
}
}
int main(){
fin >> s >> t;
n = (int)strlen(s);
m = (int)strlen(t);
precalc(s);
int index = 0;
for (int i = 0; i < m;){
if (t[i] == s[index]){
if (index == n - 1){
ans.push_back(i - n + 1);
index = a[index - 1];
}
else{
index += 1;
i += 1;
}
}
else{
if (index != 0){
index = a[index - 1];
}
else if (index != n){
i += 1;
}
}
}
fout << ans.size() << '\n';
for (int i = 0; i < min(1000, (int)ans.size()); i++){
fout << ans[i] << " ";
}
}