Pagini recente » Cod sursa (job #2070222) | Cod sursa (job #442708) | Cod sursa (job #2942935) | Cod sursa (job #477915) | Cod sursa (job #2757704)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
const int dim = 2e6+ 5;
const int baza = 73, mod = 100021,baza2=73,mod2=100007;
char a[dim],b[dim];
int hasha,hasha2;
int sol[dim];
int cnt= 0;
int main() {
in >> (a+1) >> (b+1);
int n = strlen(a+1);
int m = strlen(b+1);
int putere = 1,putere2=1;
for ( int i = 1;i <= n-1; ++i){
putere = (1LL * putere * baza)%mod;
putere2=(1LL * putere2 * baza2)%mod2;
}
for ( int i = 1; i <= n; ++i) {
hasha = ((1LL * hasha*baza)%mod + a[i])%mod;
hasha2 = ((1LL * hasha2*baza2)%mod2 + a[i])%mod2;
}
int hashb = 0,hashb2=0;
for ( int i = 1;i <= n; ++i) {
hashb = ((1LL * hashb*baza)%mod + b[i])%mod;
hashb2 = ((1LL * hashb2*baza2)%mod2 + b[i])%mod2;
}
if((hashb == hasha) && (hashb2==hasha2))
sol[++cnt] = 1;
for ( int dr = n+1; dr <= m; ++dr) {
hashb = (hashb - ((1LL * b[dr- n] * putere))%mod + mod)%mod;
hashb = ((1LL * hashb*baza))%mod;
hashb = (hashb + b[dr])%mod;
hashb2 = (hashb2 - ((1LL * b[dr- n] * putere2))%mod2 + mod2)%mod2;
hashb2 = ((1LL * hashb2*baza2))%mod2;
hashb2 = (hashb2 + b[dr])%mod2;
if((hasha == hashb) && (hasha2==hashb2))
sol[++cnt] = dr -n+1;
}
out<<cnt<<'\n';
for(int i=1;i<=cnt && i<=1000;i++)
{
out<<sol[i]-1<<" ";
}
}