Pagini recente » Cod sursa (job #1956165) | Cod sursa (job #2245665) | Cod sursa (job #2979873) | Cod sursa (job #3292596) | Cod sursa (job #3292014)
#include <bits/stdc++.h>
using namespace std;
#define BAZA 29
vector<int> hb;
int main(){
ifstream cin( "strmatch.in" );
ofstream cout( "strmatch.out" );
int i, p, ans, ha;
string a, b;
cin >> a >> b;
p = 1;
hb.resize(b.size() + 5);
ha = hb[0] = 0;
for( i = 0; i < a.size(); i++ ){
ha = ha * BAZA + ( a[i] - 'A' + 1 );
hb[1] = hb[1] * BAZA + ( b[i] - 'A' + 1 );
p *= BAZA;
}
for( i = 1; i <= b.size() - a.size(); i++ )
hb[i + 1] = hb[i] * BAZA + ( b[i + a.size() - 1] - 'A' + 1 ) - ( b[i - 1] - 'A' + 1 ) * p;
ans = 0;
for( i = 0; i <= b.size() - a.size(); i++ )
if( hb[i + 1] == ha )
ans++;
cout << ans << "\n";
for( i = 0; i <= b.size() - a.size(); i++ )
if( hb[i + 1] == ha )
cout << i << " ";
return 0;
}