Pagini recente » Cod sursa (job #2174152) | Cod sursa (job #23520) | Cod sursa (job #140892) | Cod sursa (job #2855263) | Cod sursa (job #530190)
Cod sursa(job #530190)
#include<fstream>
using namespace std;
fstream f("strmatch.in", ios::in), g("strmatch.out", ios::out);
long long L[2000002], i, t, n, m, k, nrp, v[1001];
char P[2000002], T[2000002];
int main()
{
f.getline(P,2000002);
f.getline(T,2000002);
n=strlen(P);
for(i=n; i>=0; i--)
P[i]=P[i-1];
m=strlen(T);
for(i=m; i>=0; i--)
T[i]=T[i-1];
k=0;
L[1]=0;
for(i=2; i<=n; i++)
{
while(k>0 && P[i]!=P[k+1])
k=L[k];
if(P[k+1]==P[i])
k++;
L[i]=k;
}
k=0;
nrp=0;
for(i=1; i<=m; i++)
{
while(k>0 && T[i]!=P[k+1])
k=L[k];
if(T[i]==P[k+1])
k++;
if(k==n)
{
nrp++;
if(nrp<=1000)
v[nrp]=i-n;
k=L[k];
}
}
g<<nrp<<endl;
if(nrp<=1000)
{
for(i=1; i<=nrp; i++)
g<<v[i]<<" ";
}
else
{
for(i=1; i<=1000; i++)
g<<v[i]<<" ";
}
}