Cod sursa(job #1653623)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 16 martie 2016 12:42:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <numeric>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <fstream>
#include <cstdlib>
#include <map>
#define pb push_back
#define mp make_pair
#define INF numeric_limits<int>::max()
#define bit(x) (-x)&x
#define int64 long long
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char s[2000001],x[2000001];
#define P 101
#define mod1 66013
#define mod2 56797
vector<int> match;
int main()
{
    in>>x>>s;
    int m=strlen(x),n=strlen(s);
    int h1=0,h2=0,p1=1,p2=1;
    for(int i=m-1;i>=0;i--)
    {
        h1=(h1+p1*x[i])%mod1;
        h2=(h2+p2*x[i])%mod2;
        p1=(p1*P)%mod1;
        p2=(p2*P)%mod2;
    }
    p1=p2=1;
    int c1=0,c2=0;
    for(int i=m-1;i>=0;i--)
    {
        c1=(c1+p1*s[i])%mod1;
        c2=(c2+p2*s[i])%mod2;
        if(i!=0)
        {
            p1=(p1*P)%mod1;
            p2=(p2*P)%mod2;
        }
    }
    if(c1==h1 && c2==h2)
        match.pb(0);
    for(int i=m;i<n;i++)
    {
        c1=((c1-(s[i-m]*p1)%mod1+mod1)*P+s[i])%mod1;
        c2=((c2-(s[i-m]*p2)%mod2+mod2)*P+s[i])%mod2;
        if(c1==h1 && c2==h2)
            match.pb(i-m+1);
    }
    out<<match.size()<<'\n';
    for(int i=0;i<min((int)match.size(),1000);i++)
        out<<match[i]<<' ';
    return 0;
}