Pagini recente » Atasamentele paginii Clasament nostres | Cod sursa (job #468046) | Cod sursa (job #439847) | Cod sursa (job #1749016) | Cod sursa (job #291118)
Cod sursa(job #291118)
#include <fstream>
#include <cstring>
using namespace std;
#define LMAX 2000016
int n,m,p[LMAX];
char a[LMAX],b[LMAX];
void citire()
{
ifstream fin("strmatch.in");
fin.getline(a,LMAX);
fin.getline(b,LMAX);
fin.close();
}
void prefix()
{
int k=0,x;
p[0]=p[1]=0;
for (x=2;x<=n;x++)
{
while (k>0&&a[k]!=a[x-1]) k=p[k];
if (a[k]==a[x-1]) k++;
p[x]=k;
}
}
int main()
{
citire();
n=strlen(a);
m=strlen(b);
prefix();
int k=0,nr=0;
int sol[1005];
int i;
for (i=1;i<=m;i++)
{
while (k>0 && b[i-1]!=a[k]) k=p[k];
if (a[k]==b[i-1]) k++;
if (k==n)
{
nr++;
if (nr<1001) sol[nr]=i-n;
k=p[k];
}
}
ofstream fout("strmatch.out");
fout<<nr<<"\n";
if (nr>1000) nr=1000;
for (i=1;i<=nr;i++)
fout<<sol[i]<<" ";
fout<<"\n";
fout.close();
return 0;
}