Pagini recente » Cod sursa (job #115754) | Cod sursa (job #1657572) | Cod sursa (job #858788) | Cod sursa (job #2164519) | Cod sursa (job #2796329)
#include <fstream>
using namespace std;
ifstream cin ( "strmatch.in" );
ofstream cout ( "strmatch.out" );
#define MOD (1 << 16)
#define BAZA 256
#define NMAX 1000
int pozitii_ans[NMAX];
int lg_put( int base, int power ) {
int answer;
answer = 1;
while ( power > 0 ) {
if ( power % 2 == 1 )
answer = ( answer * base ) % MOD;
base = ( base * base ) % MOD;
power = power / 2;
}
return answer;
}
int code_hash( string& s, int size ) {
int code, i;
code = 0;
for ( i = 0; i < size; i++ )
code = ( code * BAZA + s[i] ) % MOD;
return code;
}
int add_hash_character( int code, char ch ) {
return ( code * BAZA + ch ) % MOD;
}
int remove_first_character( int code, char ch, int pow ) {
code -= ch * pow % MOD;
if ( code < 0 )
code += MOD;
return code;
}
bool check( string& a, string& b, int poz ) {
int i;
i = 0;
while ( i < b.size() && i + poz < a.size() && a[i + poz] == b[i] ) {
i++;
}
return i == b.size();
}
int search( string& query, string& pattern ) {
int code_query, code_pattern, pow, i, ans;
code_query = code_hash( query, pattern.size() - 1 );
code_pattern = code_hash( pattern, pattern.size() );
pow = lg_put( BAZA, pattern.size() - 1 );
ans = 0;
i = pattern.size() - 1;
while ( i < query.size() ) {
code_query = add_hash_character(code_query, query[i] );
if ( code_pattern == code_query && check(query, pattern, i - pattern.size() + 1 ) ) {
pozitii_ans[ans++] = i;
}
code_query = remove_first_character( code_query, query[i - pattern.size() + 1], pow );
i++;
}
return ans;
}
int main() {
string a, b;
int i, ans;
cin >> a >> b;
ans = search( b, a );
cout << ans << "\n";
for ( i = 0; i < ans && i < NMAX; i++ ) {
cout << pozitii_ans[i] - a.size() + 1 << " ";
}
return 0;
}