Pagini recente » Cod sursa (job #1367402) | Cod sursa (job #2594841) | Cod sursa (job #1564424) | Cod sursa (job #2882141) | Cod sursa (job #583181)
Cod sursa(job #583181)
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int urm[2000003];
int pr[2000003];
int n,m,nr;
string t;
string p;
void urmatorul(string &c)
{
int k=-1,x;
urm[0]=0;
for(x=1;x<m;x++)
{
while(k>0&&c[k+1]!=c[x])k=urm[k];
if(c[k+1]==c[x])k++;
urm[x]=k;
}
}
int main()
{
int i,x=-1;
ifstream in("strmatch.in");
in>>p;
in>>t;
n=t.size();m=p.size();
urmatorul(p);
for(i=0;i<t.size();i++)
{
while(x>0&&p[x+1]!=t[i])x=urm[x];
if(p[x+1]==t[i])x++;
if(x==m-1)
{
pr[nr++]=i-m+1;
x=urm[x];
}
}
ofstream out("strmatch.out");
out<<nr<<'\n';
if(nr<1000)
for(i=0;i<nr;i++)
out<<pr[i]<<' ';
else
for(i=0;i<1000;i++)
out<<pr[i]<<' ';
return 0;
}