Cod sursa(job #1398261)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 24 martie 2015 08:33:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <cstring>
#include <iostream>
#define mod1 666013
#define mod2 100019

using namespace std;

string s, p;
int lenP, lenS, P1, P2, num1, num2, aux1, aux2, rez;
int S[1005];

int main()
{
    
    ifstream fi("strmatch.in");
    ofstream fo("strmatch.out");
    
    getline(fi, p);
    getline(fi, s);
    
    lenP = int( p.size() );
    lenS = int( s.size() );
    
    if (lenP > lenS)
    {
        fo << 0 << "\n";
        return 0;
    }

    num1 = num2 = 0;
    P1 = P2 = 1;
    
    for (int i = 0; i < lenP; i++)
    {
        
        num1 = (num1 * 26 + p[i]) % mod1;
        num2 = (num2 * 27 + p[i]) % mod2;
        
        if (i > 0)
        {
            P1 = (P1 * 26) % mod1;
            P2 = (P2 * 27) % mod2;
        }
        
    }
    
    aux1 = aux2 = 0;
    
    for (int i = 0; i < lenP; i++)
    {
        aux1 = (aux1 * 26 + s[i]) % mod1;
        aux2 = (aux2 * 27 + s[i]) % mod2;
    }
    
    if (aux1 == num1 && aux2 == num2)
    {
        rez++;
        S[rez] = 0;
    }
    
    for (int i = lenP; i < lenS; i++)
    {
        aux1 = ((((aux1 - (P1 * s[i - lenP])) % mod1) + mod1) * 26 + s[i]) % mod1;
        aux2 = ((((aux2 - (P2 * s[i - lenP])) % mod2) + mod2) * 27 + s[i]) % mod2;
        
        if (aux1 == num1 && aux2 == num2)
        {
            rez++;
            if (rez <= 1000)
                S[rez] = i - lenP + 1;
        }
    }
    
    fo << rez << "\n";
    for (int i = 1; i <= min(1000, rez); i++)
        fo << S[i] << " ";
    fo << "\n";
    
    fi.close();
    fo.close();
    
    return 0;
}