SUBSTR - Xâu con
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAX 1010101
#define BASE 26
typedef long long ll;
const ll mod[]={1e9+7,1e9+9,1e9+21,1e9+33};
char a[MAX];
char b[MAX];
int m,n;
ll p[4][MAX];
ll sa[4][MAX];
ll sb[4][MAX];
void init(void) {
scanf("%s",a);
scanf("%s",b);
int i,j;
m=strlen(a);
n=strlen(b);
if (n>m) exit(0);
for (i=0;i<2;i=i+1) {
p[i][0]=1;
for (j=1;j<=m;j=j+1) p[i][j]=(p[i][j-1]*BASE)%mod[i];
}
for (i=0;i<2;i=i+1) {
sa[i][0]=0;
sb[i][0]=0;
for (j=1;j<=m;j=j+1) sa[i][j]=(sa[i][j-1]+(a[j-1]-'a')*p[i][j-1])%mod[i];
for (j=1;j<=n;j=j+1) sb[i][j]=(sb[i][j-1]+(b[j-1]-'a')*p[i][j-1])%mod[i];
}
}
bool equal(int k,int a,int b) {
int i;
ll x,y;
for (i=0;i<2;i=i+1) {
x=(sa[i][a+k-1]-sa[i][a-1])%mod[i];
y=(sb[i][b+k-1]-sb[i][b-1])%mod[i];
if (a<b) x=x*p[i][b-a];
if (b<a) y=y*p[i][a-b];
if ((y-x)%mod[i]!=0) return (false);
}
return (true);
}
void process(void) {
int i,j;
for (i=1;i<=m-n+1;i=i+1)
if (equal(n,i,1)) {
printf("%d",i);
break;
}
for (j=i+1;j<=m-n+1;j=j+1)
if (equal(n,j,1)) printf(" %d",j);
}
int main(void) {
init();
process();
return 0;
}