Cod sursa(job #2025650)

Utilizator DorelBarbuBarbu Dorel DorelBarbu Data 22 septembrie 2017 23:41:21
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <map>
#include <cmath>
#include <algorithm>
#include <set>
#include <iomanip>
#include <cstdlib>
#include <iterator>
#define DBGVEC(v,lt,rt) {cout<<"Vector "<<(#v)<<" is: "; for(int i = lt; i <= rt; i++) cout<<v[i]<<' '; cout<<endl;}
#define DBG(x) {cout<<(#x)<<" = "<<x<<endl;}
using namespace std;

const int MAXN = 2*(1e6), a = 256, MOD = 1299827;
char s1[MAXN+1], s2[MAXN+1];
long long h[MAXN+1], P, hS2;
int m, n;
vector <int> sol;

long long pwr(long long a, int n)
{
    long long ans = 1;
    for(int i = 1; i <= n; i++)
    {
        ans = ans*a;
        ans %= MOD;
    }
    return ans;
}

long long computeh(char* s, int n)
{
    long long hVal = 0, p = 1;
    for(int i = n - 1; i >= 0; i--)
    {
        hVal += p*s[i];
        hVal %= MOD;
        p *= a;
        p %= MOD;
    }
    return hVal;
}

bool compareString(char* s1, char* s2)
{
    int m = strlen(s1);
    for(int i = 0; i < m; i++)
        if(s1[i] != s2[i])
            return false;
    return true;
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",s1);
    scanf("%s",s2);
    m = strlen(s1);
    n = strlen(s2);
    P = pwr(a,m);
    h[0] = computeh(s2,m);
    hS2 = computeh(s1,m);
    for(int i = 1; i <= n - m; i++)
    {
        h[i] = (a*h[i-1]) + (s2[i+m-1]) - (P*(s2[i-1]));
        while(h[i] <= 0)
            h[i] += MOD;
        h[i] %= MOD;

    }

    for(int i = 0; i <= n-m; i++)
        if(h[i] == hS2 && compareString(s1,s2+i)==true)
            sol.push_back(i);
    printf("%d\n",sol.size());
    int toPrint = min((int)sol.size(),1000);
    for(int x : sol)
    {
        toPrint--;
        printf("%d ",x);
        if(toPrint == 0)
            break;
    }
    return 0;
}