Pagini recente » Cod sursa (job #1753362) | Cod sursa (job #1084332) | Cod sursa (job #1703991) | Cod sursa (job #2204281) | Cod sursa (job #3238115)
#include <iostream>
#include <fstream>
using namespace std;
#define int long long
#define base1 37
#define base2 41
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
#define nmax 2000001
struct info{
int a, b;
bool operator == (const info&x ) const {
if( x.a == a && x.b == b )
return true;
return false;
};
};
string a, b;
info v[nmax], zero = {0, 0};
int to_number( char ch ) {
if( 'a' <= ch && ch <= 'z' )
return ch - 'a';
return ch - 'A' + 27;
}
info f( int i, int j ) {
info x = zero;
int p1 = 1, p2 = 1, k;
for( k = i; k <= j; k++ ) {
x.a = (x.a + (to_number(b[k])) * p1) % mod1;
x.b = (x.b + (to_number(b[k])) * p2) % mod2;
p1 = (p1 * base1) % mod1;
p2 = (p2 * base2) % mod2;
}
return x;
}
signed main() {
int cnt = 0, i;
info rez;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> a >> b;
for( i = a.size() - 1; i < b.size(); i++ )
v[i] = f(i - a.size() + 1, i);
for( i = 0; i < a.size(); i++ )
b[i] = a[i];
rez = f(0, a.size() - 1);
for( i = a.size() - 1; i < b.size(); i++ ) {
if( v[i] == rez )
cnt++;
}
cout << cnt << "\n";
for( i = a.size() - 1; i < b.size(); i++ ) {
if( v[i] == rez )
cout << i - a.size() + 2 << " ";
}
//cout << "\n" << rez.a << " " << rez.b << "\n";
return 0;
}