Pagini recente » Cod sursa (job #2330971) | Cod sursa (job #1431045) | Cod sursa (job #789621) | Cod sursa (job #1628198) | Cod sursa (job #2865294)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char s1[2000001];
char s2[2000001];
int lps[2000001];
int v[2000001];
int nr=0;
void lps_(char s1[], int lps[])
{
int i=1;
int j=0;
int l1=strlen(s1);
lps[0]=0;
while(i<l1)
{
if(s1[i]==s1[j])
{
j++;
lps[i]=j;
i++;
}
else{
if(j==0){
lps[i]=0;
i++;
}
else j=lps[j-1];
}
}
}
void kmp(char s1[], char s2[])
{
int i=0;
int j=0;
int l1=strlen(s1);
int l2=strlen(s2);
while(i<l2)
{
if(s2[i]==s1[j])
{
i++;
j++;
}
if(j==l1){
nr++;
v[i-j]=1;
j=lps[j-1];
}
else if(s2[i]!=s1[j]){
if(j!=0) j=lps[j-1];
else i++;
}
}
}
int main()
{
cin.get(s1,2000001);
cin.get();
cin.get(s2,2000001);
if(strlen(s1)>strlen(s2)){
cout<<"0";
return 0;
}
lps_(s1,lps);
kmp(s1,s2);
cout<<nr<<" "<<endl;
nr=0;
for(int i=0;i<=strlen(s2) && nr<1000;i++)
{
if(v[i]){
cout<<i<<" ";
nr++;
}
}
cin.close();
cout.close();
return 0;
}