Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"SneiderQuintero","updateTime":1698275350000,"title":"Procesamiento de cadenas","dislikeCnt":0,"content":"\n# Procesamiento de cadenas\n\n\n-----\n\n### Tabla de contenido\n1. Hash\n - Prerrequisitos.\n - Igualdad de cadenas.\n - Ecuación de Hash.\n - Calculo del hash de una subcadena.\n - Consultas de subcadenas.\n - Struct Hash.\n - Simple\n - Doble\n - Encontrar ocurrencias en $O(n)$.\n2. Algoritmo Z\n\t- Encontrar periodos de una cadena.\n3. Knuth - Morris - Pratt\n\t- Prefix Function\n\t- Encontrar ocurrencias\n4. Factorización de Lyndon\n5. Aho Corasick\n6. Suffix Tree\n7. Suffix Automaton\n\n-----\n\n### Algoritmos Hashing\n* Rabin-Karp algorithm para String matching.\n\n\tPrerequisitos: String hash\n\tDado un patron S y un texto T, se desea conocer los indices de las ocurrencias del patron S en el texto T.\n\n\n``` cpp\n//Tomado de cp-algorithms\nvector\u003cint\u003e rabin_karp(string const\u0026 s, string const\u0026 t) {\n\t\tconst int p \u003d 31; \n\t\tconst int m \u003d 1e9 + 9;\n\t\tint S \u003d s.size(), T \u003d t.size();\n\n\t\tvector\u003clong long\u003e p_pow(max(S, T)); \n\t\tp_pow[0] \u003d 1; \n\t\tfor (int i \u003d 1; i \u003c (int)p_pow.size(); i++) \n\t\t\t\tp_pow[i] \u003d (p_pow[i-1] * p) % m;\n\n\t\tvector\u003clong long\u003e h(T + 1, 0); \n\t\tfor (int i \u003d 0; i \u003c T; i++)\n\t\t\t\th[i+1] \u003d (h[i] + (t[i] - \u0027a\u0027 + 1) * p_pow[i]) % m; \n\t\tlong long h_s \u003d 0; \n\t\tfor (int i \u003d 0; i \u003c S; i++) \n\t\t\t\th_s \u003d (h_s + (s[i] - \u0027a\u0027 + 1) * p_pow[i]) % m; \n\n\t\tvector\u003cint\u003e occurences;\n\t\tfor (int i \u003d 0; i + S - 1 \u003c T; i++) { \n\t\t\t\tlong long cur_h \u003d (h[i+S] + m - h[i]) % m; \n\t\t\t\tif (cur_h \u003d\u003d h_s * p_pow[i] % m)\n\t\t\t\t\t\toccurences.push_back(i);\n\t\t}\n\t\treturn occurences;\n}\n```\n\tProblemas\n\t\n\t[submission:31565012]","threadId":151099,"likeCnt":2,"createTime":1688415500000,"isWorkbook":false,"viewCnt":212,"openness":2,"fav":false,"id":3773,"trustable":false}