Pagini recente » Cod sursa (job #175229) | Cod sursa (job #912854) | Cod sursa (job #2520586) | Cod sursa (job #1445106) | Cod sursa (job #3291735)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = ( 1ll << 60 ) - 1;
long long p62;
long long add_dr( long long x, int a ){
x = ( x * 62 + a ) % MOD;
return x;
}
long long rem_st(long long x, int a){
x = ( x - p62 * a % MOD + MOD ) % MOD;
return x;
}
int trans(char c){
if( 'a' <= c && c <= 'z' ){
return c - 'a' + 1;
}
if( 'A' <= c && c <= 'Z' ){
return c - 'A' + 27;
}
return c - '0' + 53;
}
vector <long long> ras;
int main(){
int i, n;
long long x, y;
string s;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
fin >> s;
x = 0;
p62 = 1;
for( i = 0; i < s.size(); i++ ){
x = add_dr( x, trans( s[i] ) );
p62 = p62 * 62 % MOD;
}
n = s.size();
//cout << x << ' ' << n << '\n';
fin >> s;
y = 0;
for( i = 0; i < s.size(); i++ ){
y = add_dr( y, trans( s[i] ) );
if( i >= n ){
y = rem_st( y, trans( s[i - n] ) );
}
//cout << y << '\n';
if( x == y ){
ras.push_back( i - n + 1 );
}
}
fout << ras.size() << '\n';
for( i = 0; i < min( ( int ) ras.size(), 1000 ); i++ ){
fout << ras[i] << ' ';
}
return 0;
}