Cod sursa(job #1776137)

Utilizator andru47Stefanescu Andru andru47 Data 10 octombrie 2016 22:55:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
#define per pair<int,int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
const int mask = 29,NMAX = 2000000 + 5;
int pw[NMAX],h1 = 0,h2 = 0;
char a[NMAX],b[NMAX];
vector <int> v;
int sol = 0;
int main()

{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(a+1);
    gets(b+1);
    int l1 = strlen(a+1);
    int l2 = strlen(b+1);
    pw[0] = 1;
    for (int i = 1; i <= l2; ++i)
        pw[i] = pw[i-1]*mask;
    if (l2<l1)
    {
        printf("0");
        return 0;
    }
    for (int i = 1; i<=l1; ++i)
        h1 += pw[i]*a[i];
    int dif = 0;
    for (int i = 1; i <= l2; ++i)
    {
        h2 += pw[i]*b[i];
        if (i<l1)continue;
        if (h1*pw[i-l1]==h2-dif)
        {

            ++sol;
            if (sol<=1000)
            v.pb(i-l1);

        }
        dif += pw[i-l1+1]*b[i-l1+1];
    }
    printf("%d\n", sol);
    for (auto &it : v)
        printf("%d ", it);

    return 0;
}