String Hashing

হ্যাশিং: হ্যাশিং একটা টেকনিক যার মাধ্যমে একটা কী(Key) ভ্যালুকে অন্য একটা ভ্যালুতে রূপান্তর করা যায়।
হ্যাশ ফাংশন: নতুন ভ্যালু বের করার যে গাণিতিক পদ্ধতি ব্যবহার করা হয় তাকে হ্যাশ ফাংশন বলে। হ্যাশ ফাংশন থেকে প্রাপ্ত ভ্যালুকে হ্যাশ ভ্যালু/হ্যাশ বলে। ভালো হ্যাশ ফাংশনে নিচের বৈশিষ্টগুলো থাকে-

• ধরি, \(X\) এবং \(Y\) দুইটি কী(Key) ভ্যালু এবং \(F()\) একটি হ্যাশ ফাংশন। এখন \(F(X)=F(Y)\) হবে যদি \(X=Y\) হয় এবং \(X\neq Y\) হলে \(F(X)\neq F(Y)\) হবে।
• ব্যবহারিক অর্থে হ্যাশ ভ্যালুর সাইজ যথেষ্ট ছোট হতে হবে।
• হ্যাশ ফাংশন সহজ ও সরল হতে হবে যাতে সহজে হ্যাশ ভ্যালু বের করা যায়।
• হ্যাশ ফাংশন এমন হতে হবে যাতে কলিশন(Collision) হওয়ার সম্ভাবনা কম থাকে।
• একমুখী হ্যাশিং ব্যবহার করতে হবে যাতে নতুন হ্যাশ ভ্যালু থেকে কী(Key) ভ্যালুতে রূপান্তর না করা যায়।

কলিশন: দুইটি ভিন্ন কী(Key) এর জন্য যদি একই হ্যাশ ভ্যালু বের হয়।

ধরি, আমরা এখন একটি স্ট্রিং \(S=``ADC"\) এর জন্য হ্যাশ ভ্যালু বের করবো। যেখানে হ্যাশ ফাংশন- \[F(S)= \sum_{i=1}^{N} X_i\] এখানে \(X_i= i\)th অ্যালফাবেটের পজিশন এবং অ্যালফাবেট \(A,B,C,...,Z\) এর পজিশন যথাক্রমে \(1,2,3,...,26\)।
\[\therefore F(S) = 1 + 4 + 3 = 8\] এখন বলতে হবে এই হ্যাশ ফাংশনটি কি ভালো? একটু চিন্তা করলেই বলা যাচ্ছে যে এই হ্যাশ ফাংশনটি ভালো না। কারণ এর কলিশন হওয়ার সম্ভাবনা অনেক বেশি। উক্ত হ্যাশ ফাংশনটি \(``ADC"\) এবং \(``ACD"\) এর জন্য একই হ্যাশ ভ্যালু দিবে।

অনেক পদ্ধতির হ্যাশ ফাংশন হতে পারে। আমরা নিচে একটি পদ্ধতি নিয়ে কাজ করবো। পদ্ধতিটি হচ্ছে-
ধরি, \(N\) সাইজের একটি স্ট্রিং \(S = S_1 S_2 ... S_N\) দেওয়া আছে। এখন হ্যাশ ফাংশন-
\[ F(S) = \sum_{i=1}^{N} X_i.P^{N-i}\] এখানে \(X_i= i\)th অ্যালফাবেটের পজিশন এবং \(P=\) বেস ভ্যালু (সাধারণত ব্যবহারিত অ্যালফাবেট সংখ্যার চাইতে বড় একটা প্রাইম নাম্বার নেওয়া হয়)। ধরি, \(P=27\), তাহলে \(F(``ADC") = 840\) এবং \(F(``ACD") = 814\).
কিন্তু এখন প্রব্লেম হচ্ছে যদি স্ট্রিং এর সাইজ অনেক বড় হয় তবে হ্যাশ ভ্যালুও অনেক বড় হয়ে যাবে। ভালো হ্যাশ ফাংশন বানানোর জন্য হ্যাশ ভ্যালু বড় হতে দেওয়া যাবে না। তাই এই প্রব্লেম এর সমাধান হিসেবে আমরা একটা কাজ করতে পারি...হ্যাশ ভ্যালুকে একটা নাম্বার দিয়ে মড করতে পারি। এখন যেকোনো নাম্বার দিয়ে মড করাটা কি Feasible?!
উত্তরটি হচ্ছে 'না'। তাহলে নাম্বারটি কেমন নিবো? এর উত্তর হচ্ছে একটা বড় প্রাইম নাম্বার নিবো। প্রাইম নাম্বার কেন নিবো? Modular Arithmetic নিয়ে আইডিয়া থাকলে এটা খুব সহজেই বুঝা যাবে। আর প্রাইমটা বড় কেন নিবো এবং কত বড় নিবো? - এই দুইটা প্রশ্নের উত্তর এখানে পাওয়া যাবে।
[To Be Continued...]

Suffix Automaton

Source :

Link1 Link2 Link3

Code :

Application :

1. Find pattern P in text T in O(|T| + |P|).

:: Build the automaton then loop through P and find if there exists transitions.

2. Find number of distinct sub-strings in S.

:: These can be calculated recursively by calculating for each node the number of different paths starting from that node. The number of different paths starting from a node is the sum of the corresponding numbers of its direct successors, plus 1 corresponding to the path that does not leave the node.

3. Total length of all distinct sub-strings in S.

:: From previous code we know value of dp[i]. Now, we will do same thing here ans[u] += ans[v] + dp[v].

4. The lexicography Kth sub-string  in S. (only distinct sub-strings / all possible sub-strings)

:: (distinct) Pick the transition with smallest character then if the path length becomes K, we will return the character and take all visited characters from that path. 

:: (Not distinct) First we will find all occurrence of each sub-strings. Then we will Find Kth smallest sub-string. See this.

[Let cnt[v] is the For all the states v number of occurrence of the sub-strings associated with v.
Initially if state v was not cloned then cnt[v] = 1 , otherwise it’s 0. We go through each state in descending order of length. and for each state we do cnt[link[v]]+=cnt[v]; After that , if u is the state corresponding to pattern P , then cnt[u] is the ans.]

5. (...)

Hashing

Source :

Link1 Link2 Link3

Code :

Application :

1. Given a text and a pattern. Find all occurrences of the pattern.

:: Check all sub-strings of length |pattern| in text & compare hash value in O(|text| + |pattern|).

2. Given two string S1 & S2. Find longest common sub-string between them.

:: Binary search on length and check them with Hash value.

3. Find lexicographic minimal cyclic shift of a string of length n.

:: See this.

4. Given a string S. Find a smallest period in it.

 :: Let answer will be of length X and it will divide |S|. Then we will check Hash value of S[0...n-x-1] & S[x...n-1] are equal or not.

5. Given two trees. Check if they are isomorphic or not.

:: Read this.

6. Read this also.

Problem :

1. NHAY - A Needle in the Haystack

2. ADAPHOTO - Ada and Terramorphing (10^6 version)

3. 1517. Freedom of Choice (10^5 version)

4. Minimal Rotation

5.  C. Watto and Mechanism

6. D. Palindrome pairs

7. E. Games on a CD

*** Solve all problems mentioned in CP algo.

Aho-Corasick

Source :

Link1 Link2

Code : 

Applications : 

1. Find all sub-stings from a given set in a text & how many times they occurs in the text. (Implemented above)

2. Find the lexicographical smallest string of a given length that does not match any given strings.

3. Find the shortest string contain all given strings.

4. Find lexicographical smallest string of length L containing K strings.

Trie (Prefix Tree)

Source : 

Link1 Link2 

Visualization : 

 Link

Code : 

Applications : 

1.Insert, Search, Remove a word from dictionary. [If there are multiple testcases then Delete the trie else it will cause MLE.]

:: Implemented in the given code.

2. Find if a word in dictionary is a prefix of another word from dictionary. 

Example : 12345, 1245, 123, 1634... Here 123 is a prefix of 12345.

:: In the time of Insertion we will check if we find a end-mark==true for a word or  after ending a word there is a child-node which is not NULL.

3. Find how many time a prefix occurs in a dictionary.

Example : algo, azzy, algea, also, else... Here "al" prefix occurs 3 times.

:: Here we will keep a counter variable in each node. In the time of insertion we will increase it each time.

4. Creating suggestion box. Given a word, print all words whose prefix is this word.

Example : algo, azzy, algea, also, else...Here "al" is given print "algo", "algea", "also".

:: Go to its child node which are not null and print them all.

5. Find maximum & minimum xor of sub-array from an array.

Example : 6 8 2 4 2 have maximum xor = 14 & minimum xor = 2.

:: Read Link2.

6. [Loading...]

Problems : 

1. 1129 - Consistency Checker   [Easy]

2. 11488 - Hyper Prefix Sets [Easy]

3. 12506 - Shortest Names [Easy]

4. Shortest Prefixes [Easy]

5. TRYCOMP - Try to complete [Medium-Easy]

6. 1269 - Consecutive Sum [Medium-Easy]

7. 1114 - Easily Readable [Easy (Try Array Implementation as Pointer Implementation will give MLE)]

8. D. Polycarp's phone book [Easy] 

9. B. A Lot of Games [Medium-Easy]

10. SUBXOR - SubXor [Medium-Easy]

11. E. Sausage Maximization [Medium-Easy]

Prefix Function (KMP)

 Source : Link

 Code : 

Application :

1. KMP (Knuth-Morris-Pratt Algorithm) - একটা string T দেওয়া আছে এর মধ্যে string P এর সকল occurrence বের করতে হবে। তো আমরা একটা নতুন string create করবো S = P + "#" + T . তারপর S এর Prefix function থেকে আমরা এর occurrence গুলা পেয়ে যাব যেখানে pi[i] = n হবে (এখানে, n = size of P) . 

2. সকল Prefix এর occurrence গণনা করতে হবে। ধরি, P একটা string, তো P[0...i] সকল prefix এর occurrence গণনা করতে হবে। 

Let, P = aabaaab  So, pi[] = 0 1 0 1 2 2 3.

আমরা cnt[pi[i]]++ করবো  এবং cnt[i] যতবার আসছে তাতে (i-1) length এর prefix ও আছে, তাই আমরা cnt[pi[i-1]] += cnt[i] করবো, সবশেষে cnt[i]++ , যেহেতু original prefix ও যোগ করতে হবে। 

So, cnt[] = 5 3 2 0 0 0 (1 - indexed). [ ith prefix occurs cnt[i] times]

vector<int> cnt(n + 1);
for (int i = 0; i < n; i++)
    cnt[pi[i]]++;
for (int i = n-1; i > 0; i--)
    cnt[pi[i-1]] += cnt[i];
for (int i = 1; i <= n; i++)
    cnt[i]++;

যদি P এর সকল prefix, T তে কতবার আছে তা বের করতে বলা হয় তবে S = P + "#" + T ধরে একই কাজ করবো। শুধু ১ম লুপটাতে i > n হবে (n = size of P) .

3.  The number of different sub-string in a string - আমাদের এক্ষেত্রে জানা থাকবে যে শুরুতে string টিতে different sub-string কয়টা আছে। তারপর string টির শেষ এ নতুন character যোগ করে ঐ নতুন string এর different sub-string কয়টা পাবো তা বের করবো। তো এখানে character যোগ করার পর string টিকে reverse করে max(pi[i]) বের করতে হবে। তারপর নতুন sub-string পাবো = |S| + 1 - max(pi[i]). [S যোগ করার আগের string].

একই ভাবে string এর শুরুতে character যোগ / বাদ দিয়ে বা শেষে যোগ / বাদ দিয়ে নতুন স্ট্রিং এর different sub-string number বের করা যায় O(n) এ । m টা operation থাকলে O(nm) complexity হবে। 

4. Compressing a string - একটা string S দেওয়া আছে এর থেকে একটা string T বানাতে হবে যত ছোট সম্ভব যাতে পাশাপাশি কয়েকটা  T যোগ করলে S পাওয়া যায়। T হবে S এর prefix, তাই S এর prefix function বের করে n - pi[n-1] করলেই আমরা T এর length পেয়ে যাবো। ধরি এই T এর length = m, এখন যদি m divides n তো m আন্সার হবে নয়তো কোনো আন্সার নাই। 

 

Some Problem Links : 

1. NAJPF - Pattern Find

2. 1255 - Substring Frequency  

3. 1258 - Making Huge Palindromes 

4. TESSER - Finding the Tesserect 

5. D. Prefixes and Suffixes

6. B. Password

7. D. MUH and Cube Walls

 

To be Continued...