Pagini recente » Cod sursa (job #144279) | Cod sursa (job #2782099) | Cod sursa (job #1387277) | Cod sursa (job #2030426) | Cod sursa (job #2976552)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int b = 65;
const int MOD = 100007;
const int MOD2 = 100021;
string p , t;
vector <int> poz;
int trans( char x ){
if( x >= 'a' ){
return x - 'a' + 1;
}
if( x >= 'A'){
return 26 + x - 'A' + 1;
}
return 52 + x - '0' + 1;
}
int main(){
fin >> p >> t;
int n = t.size();
int m = p.size();
if(m > n){
fout << 0;
exit(0);
}
int hashp = 0 , hasht = 0 , h = 1 , hash2p = 0 , hash2t = 0 , h2 = 1;
for(int i = 0 ; i < m - 1 ; i++){
h = ( h * b )%MOD;
h2 = ( h2 * b )%MOD2;
}
for(int i = 0 ; i < m ; i++){
hashp = ((hashp*b)%MOD + trans(p[i]))%MOD;
hasht = ((hasht*b)%MOD + trans(t[i]))%MOD;
hash2p = ((hash2p*b)%MOD2 + trans(p[i]))%MOD2;
hash2t = ((hash2t*b)%MOD2 + trans(t[i]))%MOD2;
}
if(hashp == hasht && hash2p == hash2t) poz.push_back(0);
for(int i = 1 ; ( i + m - 1 ) < n ; i++){
if(poz.size() == 1000) break;
hasht = (((hasht - (trans(t[i-1])*h)%MOD) * b)%MOD + trans(t[( i + m - 1 )]))%MOD;
hash2t = (((hash2t - (trans(t[i-1])*h2)%MOD2) * b)%MOD2 + trans(t[( i + m - 1 )]))%MOD2;
if(hasht == hashp && hash2p == hash2t) poz.push_back(i);
}
fout << poz.size()<< '\n';
for( auto it : poz ){
fout << it << ' ';
}
return 0;
}