Pagini recente » Cod sursa (job #2305711) | Cod sursa (job #930450) | Cod sursa (job #2559854) | Cod sursa (job #627348) | Cod sursa (job #2482116)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define ceva 2000003
using namespace std;
char a[ceva],b[ceva];
int n,m,pref[ceva],nr;
vector<int>sol;
void citire()
{
a[0]=b[0]='*';
ifstream fin("strmatch.in");
fin>>a+1>>b+1;
n=strlen(a+1);
m=strlen(b+1);
}
void prefix()
{
pref[1]=0;
for(int i=2;i<=n;i++)
{
int j=i-1;
while(j)
{
if(a[i]==a[pref[j]+1])
{
pref[i]=pref[j]+1;
break;
}
j=pref[j-1];
}
}
}
void kmp()
{
int nrc=0;
for(int i=1;i<=m;i++)
{
if(b[i]==a[nrc+1])
{
nrc++;
if(nrc==n)
{
nrc=pref[n];
sol.push_back(i-n);
nr++;
if(nr==1000)
return;
}
}
else
{
while(b[i]!=a[nrc+1]&&nrc>0)
nrc=pref[nrc];
if(b[i]==a[nrc+1])
nrc++;
}
}
}
void afisare()
{
ofstream fout("strmatch.out");
fout<<nr<<"\n";
for(int i=0;i<nr;i++)
fout<<sol[i]<<" ";
}
int main()
{
citire();
prefix();
kmp();
afisare();
return 0;
}