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