Pagini recente » Cod sursa (job #1519146) | Cod sursa (job #1994189) | Cod sursa (job #1910324) | Cod sursa (job #1097174) | Cod sursa (job #1867540)
#include <fstream>
#include <cstring>
#include <cmath>
#define NMAX 2000005
#define M101 666013
#define M109 10003
using namespace std;
struct key
{
long long b101 ;
long long b109 ;
};
struct key sir, sub;
long long k,l[NMAX];
char sir1[NMAX],sub1[NMAX];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",sub1,sir1);
int m=strlen(sub1);
int n=strlen(sir1);
long long P101 = 1;
long long P109 = 1;
for(int i=0; i<m; i++)
{
sub.b101 = (sub.b101*101+sub1[i])%M101;
sub.b109 = (sub.b109*109+sub1[i])%M109;
if(i!=0)
{
P101= (P101*101)%M101;
P109= (P109*109)%M109;
}
}
for(int i=0; i<m; i++)
{
sir.b101 = (sir.b101*101+sir1[i])%M101;
sir.b109 = (sir.b109*109+sir1[i])%M109;
}
if(sir.b101 == sub.b101 && sir.b109 == sub.b109)
l[++k]=0;
for(int i=m; i<n; i++)
{
sir.b101 = ((sir.b101 - (sir1[i-m]*P101)%M101 + M101)*101 + sir1[i])%M101;
sir.b109 = ((sir.b109 - (sir1[i-m]*P109)%M109 + M109)*109 + sir1[i])%M109;
if(sir.b101==sub.b101 && sir.b109==sub.b109)
{
l[++k]=i-m+1;
}
}
printf("%d \n",k);
for(int i=1; i<=(k<=1000?k:1000); i++)
printf("%d \n",l[i]);
return 0;
}