Pagini recente » Cod sursa (job #375600) | Cod sursa (job #209105) | Cod sursa (job #2366110) | Cod sursa (job #730357) | Cod sursa (job #2722499)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int lps[2000003],ap[1003],ans,n,m;
void formare_lps(char pattern[])
{
int index=0;
for(int i=1;i<n;)
{
if(pattern[index]==pattern[i])
{
lps[i]=index+1;
index++;
i++;
}
else if(index!=0)
index=lps[index-1];
else
{
lps[i]=0;
i++;
}
}
}
void KMP (char text[],char pattern[])
{
int i=0,j=0;
while(i<m)
{
if(text[i]==pattern[j])
{
i++;
j++;
}
else if(j!=0)
{
j=lps[j-1];
}
else
{
i++;
}
if(j==n)
{
ans++;
if(ans<=1000)
ap[ans]=i-n;
}
}
}
char text[2000003],pattern[2000003];
int main()
{
f.getline(pattern,2000003);
f.getline(text,2000003);
n=strlen(pattern);
m=strlen(text);
formare_lps(pattern);
KMP(text,pattern);
g<<ans<<"\n";
for(int i=1;i<=min(ans,1000);i++)
g<<ap[i]<<" ";
return 0;
}