Pagini recente » Cod sursa (job #2562230) | Cod sursa (job #2583825) | Cod sursa (job #780963) | Cod sursa (job #2493936) | Cod sursa (job #2811030)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
int len_a, len_b, number;
int prefix[2000001];
vector<int> result;
void read()
{
f>>a>>b;
len_a = a.length(); len_b = b.length();
a.insert(0, " "); b.insert(0, " ");
}
void precompute()
{
int q = 0;
for(int i = 2;i <= len_a;++i)
{
while(q && a[q + 1] != a[i])
q = prefix[q];
if(a[q + 1] == a[i])
++q;
prefix[i] = q;
}
}
void solve()
{
precompute();
int q = 0;
for(int i = 1;i <= len_b;++i)
{
while(q && a[q + 1] != b[i])
q = prefix[q];
if(a[q + 1] == b[i])
++q;
if(q == len_a)
{
q = prefix[q];
++number;
if(number <= 1000)
result.push_back(i - len_a);
}
}
g<<number<<'\n';
for(vector<int>::iterator it = result.begin();it != result.end();++it)
g<<*it<<" ";
}
int main()
{
read();
solve();
return 0;
}