Pagini recente » Cod sursa (job #504164) | Cod sursa (job #2128843) | Cod sursa (job #2579962) | Cod sursa (job #574593) | Cod sursa (job #627181)
Cod sursa(job #627181)
#include<fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char T[2000090],PM[2000090];
int pos[1009],nr,lgT,lgPM,P[2000090];
void P_prefix();
void KMP();
int main()
{
int a,i;
f.getline(PM+1,2000090);
lgPM=strlen(PM+1);
f.getline(T+1,200090);
lgT=strlen(T+1);
P_prefix();
KMP();
g<<nr<<'\n';\
a=1000;
if (a>nr) a=nr;
for (i=1;i<=a;++i)
g<<pos[i]<<' ';
f.close();
g.close();
return 0;
}
void KMP()
{
int k,t;
k=0;
for (t=1;t<=lgT;++t)
{
while (k&&T[t]!=PM[k+1])
k=P[k];
if (T[t]==PM[k+1])
++k;
if (k==lgPM)
{
++nr;
if (nr<=1000)
pos[nr]=t-lgPM;
k=P[k];
}
}
}
void P_prefix()
{
int p,k;
P[1]=0;
for (p=2;p<=lgPM;++p)
{
k=P[p-1];
while (PM[k+1]!=PM[p]&&k)
k=P[k];
if (PM[k+1]==PM[p])
++k;
P[p]=k;
}
}