Pagini recente » Cod sursa (job #2331334) | Cod sursa (job #2191971) | Cod sursa (job #2719319)
#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
int n, m, nr, pi[2000005];
vector<int> rez;
void Read()
{
f>>a; n = a.length(); a.insert(0, " ");
f>>b; m = b.length(); b.insert(0, " ");
}
void precompute()
{
int q = 0;
for(int i = 2;i <= n;++i)
{
while(q && a[q + 1] != a[i])
q = pi[q];
if(a[q + 1] == a[i])
++q;
pi[i] = q;
}
}
void Solve()
{
precompute();
int q = 0;
for(int i = 1;i <= m;++i)
{
while(q && a[q + 1] != b[i])
q = pi[q];
if(a[q + 1] == b[i])
++q;
if(q == n)
{
++nr;
q = pi[q];
if(nr <= 1000)
rez.push_back(i - n);
}
}
g<<nr<<'\n';
for(auto it : rez)
g<<it<<" ";
}
int main()
{
Read();
Solve();
return 0;
}