Pagini recente » Cod sursa (job #2101397) | Cod sursa (job #604872) | Cod sursa (job #1361349) | Cod sursa (job #1127939) | Cod sursa (job #3312778)
#include <bits/stdc++.h>
using namespace std;
#define MOD 100007
#define MOD2 100021
#define BAZA 62
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
string a, b;
vector<int> ans;
int main() {
int n, m, i, b1, b2, hashA, hashA2, hashB, hashB2;
fin >> a >> b;
n = a.size();
m = b.size();
b1 = b2 = 1;
hashA = hashA2 = 0;
for( i = 0; i < n; i++ ) {
hashA = ( hashA * BAZA + a[i] ) % MOD;
hashA2 = ( hashA2 * BAZA + a[i] ) % MOD2;
if( i > 0 ) {
b1 = b1 * BAZA % MOD;
b2 = b2 * BAZA % MOD2;
}
}
hashB = hashB2 = 0;
for( i = 0; i < n; i++ ) {
hashB = ( hashB * BAZA + b[i] ) % MOD;
hashB2 = ( hashB2 * BAZA + b[i] ) % MOD2;
}
if( hashA == hashB && hashA2 == hashB2 )
ans.push_back(0);
for( i = n; i < m; i++ ) {
hashB = ( ( hashB - ( b[i - n] * b1 ) % MOD + MOD ) * BAZA + b[i] ) % MOD;
hashB2 = ( ( hashB2 - ( b[i - n] * b2 ) % MOD2 + MOD2 ) * BAZA + b[i] ) % MOD2;
if( hashA == hashB && hashA2 == hashB2 )
ans.push_back(i - n + 1);
}
if( ans.size() < 1000 ) {
fout << ans.size() << '\n';
for( int x : ans )
fout << x << ' ';
} else {
fout << ans.size() << '\n';
for( i = 0; i < 1000; i++ )
fout << ans[i] << ' ';
}
return 0;
}