Pagini recente » Cod sursa (job #2468032) | Cod sursa (job #93041) | Cod sursa (job #2154090) | Cod sursa (job #2044590) | Cod sursa (job #1979847)
#include<cstdio>
#include<cstring>
#include<vector>
#define MODA 666013
#define MODB 1000007
#define BASE 62
using namespace std;
int poz(char c){
if(c>='0'&&c<='9')
return c-'0';
else if(c>='a'&&c<='z')
return c-'a'+10;
else
return c-'A'+36;
}
char a[2000001];
char b[2000001];
vector <int> v;
int main(){
int n,m,nr1a,nr1b,nr2a,nr2b,pa,pb,i,ca,cb,nr;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",a);
n=strlen(a);
pa=pb=1;
nr1a=nr1b=0;
for(i=0;i<n;i++){
nr1a=(nr1a*BASE+poz(a[i]))%MODA;
nr1b=(nr1b*BASE+poz(a[i]))%MODB;
if(i>0){
pa=(pa*BASE)%MODA;
pb=(pb*BASE)%MODB;
}
}
scanf("%s",b);
m=strlen(b);
nr2a=nr2b=0;
for(i=0;i<n-1;i++){
nr2a=(nr2a*BASE+poz(b[i]))%MODA;
nr2b=(nr2b*BASE+poz(b[i]))%MODB;
}
nr=0;
for(i=n-1;i<m;i++){
nr2a=(nr2a*BASE+poz(b[i]))%MODA;
nr2b=(nr2b*BASE+poz(b[i]))%MODB;
if(nr2a==nr1a&&nr2b==nr1b&&v.size()<1000){
v.push_back(i-n+1);
nr++;
}
ca=(pa*poz(b[i-n+1]))%MODA;
nr2a-=ca;
if(nr2a<0)
nr2a+=MODA;
cb=(pb*poz(b[i-n+1]))%MODB;
nr2b-=cb;
if(nr2b<0)
nr2b+=MODB;
}
printf("%d\n",nr);
for(i=0;i<v.size();i++)
printf("%d ",v[i]);
}