Pagini recente » Clasament oni2015.1112.bv.1 | Cod sursa (job #2037171) | Cod sursa (job #3159995) | Cod sursa (job #1221801) | Cod sursa (job #3168470)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m, t;
string a, b;
vector<int> r, p;
int main()
{
f >> a >> b;
p.resize(n+3);
n = a.size(); m = b.size();
a = '#' + a; b = '#' + b;
for (int i = 2; i <= n; i++){
int k = p[i-1];
while (k && a[i] != a[k+1]) k = p[k];
if (a[i] == a[k+1]) k++;
p[i] = k;
}
int k = 0;
for (int i = 1; i <= m; i++){
while (k && b[i] != a[k+1]) k = p[k];
if (b[i] == a[k+1]) k++;
if (k == n){
t++; k = p[n];
if (t <= 1000) r.pb(i-n);
}
}
g << t << '\n';
for (auto it: r) g << it << ' ';
return 0;
}