fork download
copy 
  1. // Problema: Counting Patterns
  2. // Descripcion: Dada una cadena de texto, responder queries rapidamente que digan cuantas veces se encuentra una cadena de texto dada en el texto original
  3. // Juez Virtual: https://c...content-available-to-author-only...s.fi/problemset/task/2103
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. // Construye el suffix array usando el algoritmo de doubling + counting sort.
  9. // Devuelve un vector con las posiciones de los sufijos del string original (sin '$').
  10. vector<int> construct_suffix_array(string& s) {
  11.     s += "$"; // sentinel más pequeño que cualquier otro carácter
  12.  
  13.     int n = s.length();
  14.     int alphabet = max(256, n); // tamaño del contador (al menos 256 para caracteres)
  15.  
  16.     vector<int> suffix_array(n), rank(n), cnt(alphabet);
  17.  
  18.     // conteo inicial por carácter
  19.     for (int i = 0; i < n; i++) {
  20.         cnt[s[i]]++;
  21.     }
  22.  
  23.     // prefijos acumulados para counting sort
  24.     for (int i = 1; i < alphabet; i++) {
  25.         cnt[i] += cnt[i - 1];
  26.     }
  27.  
  28.     // construir SA ordenando por primer carácter
  29.     for (int i = 0; i < n; i++) {
  30.         suffix_array[--cnt[s[i]]] = i;  
  31.     }
  32.  
  33.     // asignar clases iniciales (rank) según carácter
  34.     rank[suffix_array[0]] = 0;
  35.     for (int i = 1; i < n; i++) {
  36.         if (s[suffix_array[i]] != s[suffix_array[i - 1]]) {
  37.             rank[suffix_array[i]] = rank[suffix_array[i - 1]] + 1;
  38.         }
  39.         else {
  40.             rank[suffix_array[i]] = rank[suffix_array[i - 1]];
  41.         }
  42.     }
  43.  
  44.     vector<int> new_suffix_array(n), new_rank(n);
  45.  
  46.     // bucle de doubling: longitudes 1,2,4,... hasta cubrir n
  47.     for (int k = 0; (1 << k) < n; k++) {
  48.         // desplazamos sufijos para ordenar por la segunda mitad (radix step)
  49.         for (int i = 0; i < n; i++) {
  50.             new_suffix_array[i] = (suffix_array[i] - (1 << k) + n) % n;
  51.         }
  52.  
  53.         // volver a usar cnt para ordenar por la primera clave (rank)
  54.         fill(cnt.begin(), cnt.end(), 0);
  55.  
  56.         for (int i = 0; i < n; i++) {
  57.             cnt[rank[new_suffix_array[i]]]++;
  58.         }
  59.  
  60.         for (int i = 1; i < alphabet; i++) {
  61.             cnt[i] += cnt[i - 1];
  62.         }
  63.  
  64.         for (int i = n - 1; i >= 0; i--) {
  65.             suffix_array[--cnt[rank[new_suffix_array[i]]]] = new_suffix_array[i];  
  66.         }
  67.  
  68.         // recalcular nuevas clases (ranks) basadas en pares
  69.         new_rank[suffix_array[0]] = 0;
  70.  
  71.         for (int i = 1; i < n; i++) {
  72.             pair<int, int> prev = {rank[suffix_array[i - 1]], rank[(suffix_array[i - 1] + (1 << k)) % n]};
  73.             pair<int, int> cur = {rank[suffix_array[i]], rank[(suffix_array[i] + (1 << k)) % n]};
  74.  
  75.             if (prev != cur) {
  76.                 new_rank[suffix_array[i]] = new_rank[suffix_array[i - 1]] + 1;
  77.             }
  78.             else {
  79.                 new_rank[suffix_array[i]] = new_rank[suffix_array[i - 1]];
  80.             }
  81.         }
  82.  
  83.         swap(rank, new_rank); // actualizar ranks para la siguiente iteración
  84.     }
  85.  
  86.     s.pop_back(); // quitar sentinel del string original
  87.     suffix_array.erase(suffix_array.begin()); // quitar la entrada correspondiente al '$'
  88.     return suffix_array;
  89. }
  90.  
  91. int main() {
  92.     cin.tie(0);
  93.     ios_base::sync_with_stdio(0);
  94.  
  95.     string s;
  96.     cin >> s;
  97.     int n = s.length();
  98.  
  99.     vector<int> suffix_array = construct_suffix_array(s);
  100.  
  101.     int q;
  102.     cin >> q;
  103.  
  104.     // Para cada patrón, hacemos dos búsquedas binarias sobre el SA
  105.     while (q--) {
  106.         string t;
  107.         cin >> t;
  108.  
  109.         int l = 0;
  110.         int r = n;
  111.  
  112.         // búsqueda del límite superior (<= t)
  113.         while (r - l > 1) {
  114.             int m = (l + r) / 2;
  115.  
  116.             // comparar prefijo del sufijo con t (aquí se copia con substr)
  117.             string suffix = s.substr(suffix_array[m], t.length());
  118.  
  119.             if (suffix <= t) 
  120.                 l = m;
  121.             else
  122.                 r = m;
  123.         }
  124.  
  125.         int upper = l;
  126.  
  127.         l = 0;
  128.         r = n; 
  129.  
  130.         // búsqueda del límite inferior (< t)
  131.         while (r - l > 1) {
  132.             int m = (l + r) / 2;
  133.             string suffix = s.substr(suffix_array[m], t.length());
  134.  
  135.             if (suffix < t)
  136.                 l = m;
  137.             else
  138.                 r = m;
  139.         }
  140.  
  141.         int lower = l;
  142.  
  143.         // verificar coincidencias exactas en los extremos encontrados
  144.         string suffix_lower = s.substr(suffix_array[lower], t.length());
  145.         string suffix_upper = s.substr(suffix_array[upper], t.length());
  146.  
  147.         if (suffix_lower == t) lower--;
  148.         if (suffix_upper != t) upper = 0;
  149.  
  150.         int ans = max(0, upper - lower);
  151.         cout << ans << endl;
  152.     }
  153. }
  154.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
aybabtu
3
bab
abc
a
stdout
copy 
1
0
2
https://ideone.com/To3oQL
language:
C++ (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!