Cod sursa(job #2222868)

Utilizator claudiu.gatinaFMI Claudiu Gatina claudiu.gatina Data 18 iulie 2018 13:04:16
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define NMAX 2000001
#define PRIM1 48487
#define PRIM2 59197

using namespace std;

int hash1, hash2;
char a[NMAX], b[NMAX];

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s", &a);
    scanf("%s", &b);
    int sizeA = strlen(a);
    for(int i = 0; i < sizeA; ++i)
    {
      hash1 = (hash1 + a[i]) % PRIM1;
      hash2 = (hash2 + a[i]) % PRIM2;
    }
    int bHash1 = 0;
    int bHash2 = 0;
    for(int i = 0; i < sizeA - 1; ++i)
    {
      bHash1 = (bHash1 + b[i]) % PRIM1;
      bHash2 = (bHash2 + b[i]) % PRIM2;
    }
    vector<int> ans;
    for(int i = sizeA - 1; b[i] != NULL; ++i)
    {
      bHash1 = (bHash1 + b[i]) % PRIM1;
      bHash2 = (bHash2 + b[i]) % PRIM2;
      int beginPos = i - sizeA + 1;
      if(hash1 == bHash1 && hash2 == bHash2)
      {
        int ok = 1;
        for(int j = beginPos; j <= i; ++j)
        {
          if(a[j - beginPos] != b[j])
          {
            ok = 0;
            break;
          }
        }
        if(ok)
        {
          ans.push_back(beginPos);
        }
      }
      bHash1 = (bHash1 - b[beginPos] + PRIM1) % PRIM1;
      bHash2 = (bHash2 - b[beginPos] + PRIM2) % PRIM2;
    }
    printf("%d\n", ans.size());
    for(int i = 0; i < ans.size() && i < 1000; ++i)
      printf("%d ", ans[i]);
    return 0;
}