Question

Good resources for string searching algorithms in competitive programming ?

Answer 1

https://www.codechef.com/problems/CONVSTR

https://codeforces.com/problemset/problem/1383/A

https://www.hackerearth.com/practice/algorithms/string-algorithm/string-searching/practice-problems/algorithm/strongest-string-4103a929/

https://codeforces.com/contest/1511/problem/D 

https://www.codechef.com/DCAT2021/problems/DECOANA  

https://leetcode.com/problems/find-the-most-competitive-subsequence/ 

https://discuss.codechef.com/t/artbalan-editorial/21970/5 

https://www.codechef.com/COOK109A/problems/RICHSTR/   

https://www.codechef.com/COOK103B/problems/SECPASS  

https://www.codechef.com/COOK125A/problems/SEDPASS  

https://www.codechef.com/problems/SKMP 

https://www.codechef.com/problems/CHEFSHIP

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000201bfe/0000000000201c96

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74/00000000002b3034

Resource : - https://cp-algorithms.com/string/prefix-function.html

Problem--->https://www.codechef.com/CENS2020/problems/CENS20C

Z-algorithm

Problem : - https://www.codechef.com/problems/CHEFSHIP

Resource : - https://cp-algorithms.com/string/z-function.html

Hashing : -

Resource : - https://cp-algorithms.com/string/string-hashing.html.

Implementation : - https://ideone.com/ClQhjz

4)Rabin-Karp : - Tell how many times the given pattern occurs in our string and enumerate all the occurrences.

Resource : -https://cp-algorithms.com/string/rabin-karp.html

5)Aho-ho : -(Related-tot-trie)

https://cp-algorithms.com/string/aho_corasick.html

6)Suffix-Stuff : - 

https://cp-algorithms.com/string/suffix-array.html

https://cp-algorithms.com/string/main_lorentz.html

https://cp-algorithms.com/string/suffix-automaton.html

https://cp-algorithms.com/string/suffix-tree-ukkonen.html

7)Manachar’s algorithm and some Palindromic-Philosophy : ---- > 

Problems : https://codeforces.com/contest/1326/problem/D1

1)Palindromic-Substring:-->https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/

https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/

 

2)Focus on this problem:--->https://www.codechef.com/INQU2019/problems/INQU1900

 

3)Then:--->https://www.codechef.com/COOK63/problems/PP

 

4)Then:------>https://www.hackerearth.com/practice/algorithms/dynamic-programming/2-dimensional/practice-problems/algorithm/palindromes-everywhere-64f67313/

 

5)Now:-->https://discuss.codechef.com/t/klpm-editorial/23265

https://ide.codingblocks.com/s/69585

 

6)DP:->>https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/palindrome-game-dcf03e89/

 

7)More : - https://codeforces.com/contest/1326/problem/D2

 

Palindromic Philosophy : https://leetcode.com/problems/maximize-palindrome-length-from-subsequences/ 

 

Dynamic-Programming mixing up with strings : 

1)https://leetcode.com/problems/find-all-good-strings/

2)https://www.geeksforgeeks.org/given-two-strings-find-first-string-subsequence-second/

3)LSI:- https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

 

6)https://codeforces.com/problemset/problem/1096/D

7)https://codeforces.com/problemset/problem/676/C

8)https://www.geeksforgeeks.org/edit-distance-dp-5/

9)https://codeforces.com/problemset/problem/346/B

 

Answer 2

https://cp-algorithms.com/

https://www.hackerearth.com/practice/algorithms/string-algorithm/string-searching/tutorial/

- Z algorithm by paladin8

- Suffix Automata by quasisphere

- Transition between Z- and prefix functions by adamant

- Manacher's algorithm and code readability by adamant