Pagini recente » Cod sursa (job #3212608) | Cod sursa (job #115885) | Cod sursa (job #844634) | Cod sursa (job #2533200) | Cod sursa (job #1070578)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
string a,b;
vector <int> r;
int pre[2000005],i,pos;
int main(void)
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a;
f>>b;
pre[0]=-1;
for (i=1;i<a.size();i++)
{
pos=pre[i-1];
while ((pos>=0)&&(a[pos+1]!=a[i]))
pos=pre[pos];
if (a[pos+1]==a[i])
pre[i]=pos+1;
else
pre[i]=-1;
}
pos=-1;
for (i=0;i<b.size();i++)
{
while ((pos>=0)&&(a[pos+1]!=b[i]))
pos=pre[pos];
if (a[pos+1]==b[i])
pos++;
if (pos+1==a.size())
{
if (r.size()<1000)
r.push_back((i+1)-a.size());
}
}
g<<r.size()<<'\n';
for (i=0;i<r.size();i++)
g<<r[i]<<' ';
return 0;
}