Pagini recente » Cod sursa (job #2690201) | Cod sursa (job #2646641) | Cod sursa (job #2843449) | Cod sursa (job #475196) | Cod sursa (job #1938001)
#include <bits/stdc++.h>
//strmatch cu Z-algorithm
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int N = 2000010;
char A[N],B[N],*p;
int n,m,i,j,st,dr,nr,ZT,Z[N];
vector<int> sol;
void zfunction(),pfunction();
int main()
{
A[0]='#';p=A+1;f>>p;n=strlen(p);p[n+1]='@';
B[0]='#';p=B+1;f>>p;m=strlen(p);p[m+1]='&';
zfunction();pfunction();
g<<nr<<'\n';
for(auto it:sol)
g<<it<<' ';
return 0;
}
void zfunction()
{
for(i=2; i<=n; i++)
{
if(i<=dr&&i+Z[i-st+1]-1<dr)
Z[i]=Z[i-st+1];
else if(i<=dr)
{
j=dr-i+1;
st=i;
while(A[dr+1]==A[j+1])
dr++,j++;
Z[i]=j;
}
else if(A[i]==A[1])
{
st=dr=i;
j=1;
while(A[dr+1]==A[j+1])
dr++,j++;
Z[i]=j;
}
}
}
void pfunction()
{
//Z[1]=n;
st=dr=0;
for(i=1; i<=m; i++)
{
ZT=0;
if(i<=dr&&i+Z[i-st+1]-1<dr)
ZT=Z[i-st+1];
else if(i<=dr)
{
j=dr-i+1;
st=i;
while(B[dr+1]==A[j+1]&&j<n)
dr++,j++;
ZT=j;
}
else if(B[i]==A[1])
{
st=dr=i;
j=1;
while(B[dr+1]==A[j+1]&&j<n)
dr++,j++;
ZT=j;
}
if(ZT==n)
{
nr++;
if(nr<1000)
sol.push_back(i-1);
}
cout<<ZT;
}
}