Pagini recente » Cod sursa (job #2755796) | Cod sursa (job #44785) | Cod sursa (job #2559716) | Borderou de evaluare (job #528067) | Cod sursa (job #2791155)
#include <fstream>
#include <cstring>
#include <map>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int p, ind;
const int NMAX=2e6 + 7;
const int mod=1e9 + 7;
char a[NMAX],b[NMAX];
int poz[1003];
map <long long,int> m;
long long x, y, pow;
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
long long getCode(char c){
if('a'<=c && c<='z')
return c-'a'+1;
else if('A'<=c && c<='Z')
return c-'A'+27;
return c-'0'+53;
}
int main() {
int n,m;
a[0]='a';
b[0]='a';
cin>>(a+1);
cin>>(b+1);
n=strlen(a)-1;
m=strlen(b)-1;
x=0;
pow=1;
for(int i=1;i<=n;i++){
x=(x*63+getCode(a[i]))%mod;
y=(y*63+getCode(b[i]))%mod;
if(i!=1)
pow*=63;
pow%=mod;
}
for(int i=1;i<=m-n+1;i++){
if(x==y) {
++p;
if(ind<1000)
poz[++ind]=i;
}
y-=getCode(b[i])*pow;
y%=mod;
if(y<0)
y+=mod;
y=y*63+getCode(b[i+n]);
y%=mod;
}
cout<<p<<'\n';
for(int i=1;i<=ind;i++)
cout<<poz[i] - 1<<' ';
cout<<'\n';
return 0;
}