Cod sursa(job #1527869)

Utilizator ThomasFMI Suditu Thomas Thomas Data 18 noiembrie 2015 19:57:05
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

#define LMax 2000005
#define P 317

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char A[LMax], B[LMax];
int n, m;
unsigned long long h1, h2, PP = 1LL;
vector<int> sol;

int main()
{
    f>>A>>B;
    n = strlen(A);
    m = strlen(B);

    int i;
    for(i=0;i<n;++i) h1 = h1 * P + A[i], h2 = h2 * P + B[i];
    for(i=1;i<n;++i) PP *= P;
    if(h1 == h2) sol.push_back(1);
    for(i=n;i<m;++i)
    {
        h2 -= B[i-n] * PP;
        h2 = h2 * P + B[i];
        if(h1 == h2) sol.push_back(i-n+1);
    }
    g<<sol.size()<<"\n";
    int x = min(1000, (int)sol.size());
    for(i=0;i<x;++i) g<<sol[i]<<" ";

    f.close();
    g.close();
    return 0;
}