Pagini recente » Cod sursa (job #286028) | Cod sursa (job #2624) | Cod sursa (job #1149091) | Cod sursa (job #1656327) | Cod sursa (job #1867456)
#include <fstream>
#include <cstring>
#include <cmath>
#define NMAX 2000000
#define M101 666013
#define M109 10003
using namespace std;
ifstream a("strmatch.in");
ofstream b("strmatch.out");
struct key { int b101 ; int b109 ;};
struct key sir[NMAX], sub;
int k,l[NMAX];
char sir1[NMAX],sub1[NMAX];
int pww(int x,int t)
{
int p=1;
for(int i=1;i<=t;i++)
p*=x;
return p;
}
int main()
{
a>>sub1>>sir1;
int m=strlen(sub1);
int n=strlen(sir1);
for(int i=0;i<m;i++)
{
int x=pww(101,m-i-1);
sub.b101 += sub1[i]*pww(101,m-i-1);
sub.b109 += sub1[i]*pww(109,m-i-1);
}
sub.b101 %= M101;
sub.b109 %= M109;
for(int i=0;i<m;i++)
{
sir[m-1].b101 += sir1[i]*pww(101,m-i-1);
sir[m-1].b109 += sir1[i]*pww(109,m-i-1);
}
sir[m-1].b101 %= M101;
sir[m-1].b109 %= M109;
long long int P101 = pww(101,m-1);
long long int P109 = pww(109,m-1);
for(int i=m;i<n;i++)
{
sir[i].b101 = ((( sir[i-1].b101 - (int)sir1[i-m]*P101)%M101 + M101 )*101 + sir1[i] )%M101;
sir[i].b109 = ((( sir[i-1].b109 - (int)sir1[i-m]*P109)%M109 + M109 )*109 + sir1[i] )%M109;
if(sir[i].b101==sub.b101 && sir[i].b109==sub.b109)
{
bool ok=true;
for(int k=i-m+1,u=0;k<=i;k++,u++)
if(sir1[k]!=sub1[u])
ok=false;
if(ok)
{
l[++k]=i-m+1;
}
}
}
b<<k<<endl;
for(int i=1;i<=k;i++)
b<<l[i]<<" ";
return 0;
}