Pagini recente » Cod sursa (job #1569936) | Cod sursa (job #1180889) | Cod sursa (job #2998819) | Cod sursa (job #2775489) | Cod sursa (job #1070580)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
string a,b;
vector <int> r;
int pre[2000005],i,pos,rs;
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())
r.push_back((i+1)-a.size());
}
g<<r.size()<<'\n';
rs=r.size();
for (i=0;i<min(1000,rs);i++)
g<<r[i]<<' ';
return 0;
}