Pagini recente » Cod sursa (job #1721807) | Cod sursa (job #519039) | Cod sursa (job #3169068) | Cod sursa (job #935786) | Cod sursa (job #2722487)
#include <bits/stdc++.h>
using namespace std;
int lps[1000],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[1000],pattern[1000];
int main()
{
cin.getline(pattern,1000);
cin.getline(text,1000);
formare_lps(pattern);
KMP(text,pattern);
cout<<ans<<"\n";
for(int i=1;i<=min(ans,1000);i++)
cout<<ap[i]<<" ";
return 0;
}