Cod sursa(job #899166)

Utilizator rootsroots1 roots Data 28 februarie 2013 13:10:58
Problema Potrivirea sirurilor Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <string>
#include <vector>

#define B1 29
#define B2 71
#define mod 999983

using namespace std;

ifstream cin;
ofstream cout;

vector < int > sol;

string a, b;

int main()
{
    cin.open("strmatch.in");
    cout.open("strmatch.out");

    getline(cin, a);
    getline(cin, b);

    int N = a.size();
    int M = b.size();

    int cod1 = 0;
    int cod2 = 0;
    for(int i = 0; i < N; ++ i)
    {
        cod1 = (cod1 * B1 + a[i] - 'A') % mod;
        cod2 = (cod2 * B2 + a[i] - 'A') % mod;
    }

    int pw1 = 1;
    int pw2 = 1;
    for(int i = 1; i < N; ++ i)
    {
        pw1 = (pw1 * B1) % mod;
        pw2 = (pw2 * B2) % mod;
    }

    int pre1 = 0;
    int pre2 = 0;
    for(int i = 0; i < N; ++ i)
    {
        pre1 = (pre1 * B1 + b[i] - 'A') % mod;
        pre2 = (pre2 * B2 + b[i] - 'A') % mod;
    }

    if(cod1 == pre1 && cod2 == pre2) sol.push_back(1);

    for(int i = N; i < M; ++ i)
    {
        pre1 = (pre1 - ((b[i - N] - 'A') * pw1) % mod + mod) % mod;
        pre2 = (pre2 - ((b[i - N] - 'A') * pw2) % mod + mod) % mod;

        pre1 *= B1;
        pre2 *= B2;

        pre1 += b[i] - 'A';
        pre2 += b[i] - 'A';

        pre1 %= mod;
        pre2 %= mod;

        if(cod1 == pre1 && cod2 == pre2) sol.push_back(i - N + 1);
    }

    cout << sol.size() << '\n';
    for(int i = 0; i < 1000 && i < sol.size(); ++ i)
        cout << sol[i] << ' ';
    cout << '\n';


    cin.close();
    cout.close();

    return 0;
}