Pagini recente » Cod sursa (job #2223611) | Cod sursa (job #539650) | Cod sursa (job #2978540) | Cod sursa (job #93393) | Cod sursa (job #2656430)
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int lps[2000005],v[2000005];
char A[2000005],B[2000005];
void BuildLPS()
{
int i,len;
len=0;
lps[0]=0;
i=1;
while (i<strlen(B))
{
if (B[i]==B[len])
{
len++;
lps[i]=len;
i++;
}
else
{
if (len!=0)
{
len=lps[len-1];
}
else
{
lps[i]=0;
i++;
}
}
}
}
void KMP()
{
int i,j,k;
i=j=k=0;
while (i<strlen(A))
{
if (A[i]==B[j])
{
i++;
j++;
}
if (j==strlen(B))
{
v[++k]=i-j;
j=lps[j-1];
}
else if (i<strlen(A) && B[j]!=A[i])
{
if (j)
j=lps[j-1];
else i++;
}
}
g<<k<<'\n';
for (i=1;i<=k;i++) g<<v[i]<<" ";
}
int main()
{
f>>B;
f>>A;
BuildLPS();
KMP();
return 0;
}