Pagini recente » Cod sursa (job #2409580) | Cod sursa (job #1662554) | Cod sursa (job #1508577) | Cod sursa (job #2388253) | Cod sursa (job #2929203)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int NM = 2e6 + 2;
char s[NM], t[NM];
int n, m, a[NM], ans;
vector<int>v;
void precalc(char s[], int n){
a[0] = 0;
int index = 0;
for (int i = 1; i < n;){
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(t, m);
for (int i = 0, index = 0; i < m;){
if (t[i] == s[index]){///match
if (index == n - 1){
if (int(v.size()) < 1000){
ans += 1;
v.push_back(i - n + 1);
}
index = a[index - 1];
}
else{
index += 1;
i += 1;
}
}
else{
if (index != 0){
index = a[index - 1];
}
else{
i += 1;
}
}
}
fout << ans << '\n';
for (int x : v){
fout << x << " ";
}
}