Pagini recente » Cod sursa (job #1617444) | Istoria paginii runda/eusebiu_oji_2021_cls11-12/clasament | Cod sursa (job #1520990) | Istoria paginii runda/oni_2010_ramas | Cod sursa (job #1951925)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMax = 2e6 + 5;
int Pi[NMax];
vector < int > v;
int main() {
ios::sync_with_stdio(false);
string a, b;
fin >> a >> b;
int n = (int)a.size();
int m = (int)b.size();
a = '$' + a;
b = '$' + b;
int k = 0;
for(int i = 2; i <= n; i++) {
while(k > 0 && a[k + 1] != a[i]) {
k = Pi[k];
}
if(a[k + 1] == a[i]) k++;
Pi[i] = k;
}
int ans = 0;
k = 0;
for(int i = 1; i <= m; i++) {
while(k > 0 && a[k + 1] != b[i]) {
k = Pi[k];
}
if(a[k + 1] == b[i]) k++;
if(k == n) {
ans++;
v.push_back(i - n);
}
}
fout << ans << "\n";
for(int i = 0; i < min((int)v.size(), 1000); i++) fout << v[i] << " ";
return 0;
}