Pagini recente » Cod sursa (job #984612) | Cod sursa (job #2946217) | Cod sursa (job #2291637) | Cod sursa (job #3225395) | Cod sursa (job #3225438)
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define pb push_back
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int N = 2000005;
int n, m, p[N];
string a, b;
int cnt;
queue<int> sol;
int main()
{
fin.tie(0); fout.tie(0);
ios_base::sync_with_stdio(0);
fin >> a >> b;
n = a.size(); m = b.size();
a = '*' + a; b = '*' + b;
for (int i = 2; i <= n; i++){
int pos = p[i-1];
while (pos && a[pos+1] != a[i]) pos = p[pos];
if (a[pos+1] == a[i]) pos++;
p[i] = pos;
}
int pos = 0;
for (int i = 1; i <= m; i++){
while (pos && b[i] != a[pos+1]) pos = p[pos];
if (b[i] == a[pos+1]) pos++;
if (pos == n){
cnt++; pos = p[pos];
if (cnt <= 1000) sol.push(i - n);
}
}
fout << cnt << '\n';
while (!sol.empty()){ fout << sol.front() << ' '; sol.pop(); }
return 0;
}