Rabin Karp (hashing) String pattern matching

Important algorithms (3 Part Series)

1 Kadane’s Algorithm
2 Knuth Morris Prat algorithm[Pattern Matching]
3 Rabin Karp (hashing) String pattern matching

Problem

TC:O(n) and SC: O(n)

<span>// using rabin karp hashing approach</span>
<span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>String</span> <span>shortestPalindrome</span><span>(</span><span>String</span> <span>s</span><span>)</span> <span>{</span>
        <span>int</span> <span>prefix</span> <span>=</span> <span>0</span><span>;</span>
        <span>int</span> <span>suffix</span> <span>=</span> <span>0</span><span>;</span>
        <span>int</span> <span>lastIndex</span> <span>=-</span><span>1</span><span>;</span>
        <span>int</span> <span>base</span> <span>=</span> <span>29</span><span>;</span>
        <span>int</span> <span>power</span> <span>=</span> <span>1</span><span>;</span>
        <span>int</span> <span>mod</span> <span>=</span> <span>(</span><span>int</span><span>)(</span><span>1</span><span>e9</span> <span>+</span> <span>7</span><span>);</span>
        <span>String</span> <span>str</span> <span>=</span> <span>""</span><span>;</span>
        <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>s</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span>
            <span>int</span> <span>ch</span> <span>=</span> <span>(</span><span>s</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>)-</span><span>'a'</span><span>)</span> <span>+</span><span>1</span><span>;</span>
            <span>prefix</span> <span>=</span> <span>(</span><span>int</span><span>)((</span><span>1L</span> <span>*</span> <span>prefix</span> <span>*</span> <span>base</span><span>)</span> <span>%</span> <span>mod</span><span>);</span>
            <span>prefix</span> <span>=</span> <span>(</span><span>int</span><span>)((</span><span>prefix</span> <span>+</span> <span>ch</span><span>)</span> <span>%</span> <span>mod</span><span>);</span>
            <span>suffix</span> <span>=</span> <span>(</span><span>int</span><span>)((</span><span>suffix</span> <span>+</span> <span>1L</span> <span>*</span> <span>ch</span> <span>*</span> <span>power</span><span>)</span> <span>%</span> <span>mod</span><span>);</span>
            <span>power</span> <span>=</span> <span>(</span><span>int</span><span>)((</span><span>1L</span> <span>*</span> <span>power</span> <span>*</span> <span>base</span><span>)</span> <span>%</span> <span>mod</span><span>);</span>
            <span>if</span><span>(</span><span>prefix</span> <span>==</span> <span>suffix</span><span>){</span>
                <span>lastIndex</span> <span>=</span><span>i</span><span>;</span>
            <span>}</span>
        <span>}</span>
        <span>str</span> <span>=</span> <span>s</span><span>.</span><span>substring</span><span>(</span><span>lastIndex</span><span>+</span><span>1</span><span>);</span>
        <span>return</span> <span>new</span> <span>StringBuilder</span><span>(</span><span>str</span><span>).</span><span>reverse</span><span>().</span><span>toString</span><span>()+</span><span>s</span><span>;</span>
    <span>}</span>
<span>}</span>
<span>// using rabin karp hashing approach</span>

<span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>String</span> <span>shortestPalindrome</span><span>(</span><span>String</span> <span>s</span><span>)</span> <span>{</span>
        <span>int</span> <span>prefix</span> <span>=</span> <span>0</span><span>;</span>
        <span>int</span> <span>suffix</span> <span>=</span> <span>0</span><span>;</span>
        <span>int</span> <span>lastIndex</span> <span>=-</span><span>1</span><span>;</span>
        <span>int</span> <span>base</span> <span>=</span> <span>29</span><span>;</span>
        <span>int</span> <span>power</span> <span>=</span> <span>1</span><span>;</span>
        <span>int</span> <span>mod</span> <span>=</span> <span>(</span><span>int</span><span>)(</span><span>1</span><span>e9</span> <span>+</span> <span>7</span><span>);</span>
        <span>String</span> <span>str</span> <span>=</span> <span>""</span><span>;</span>
        <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>s</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span>
            <span>int</span> <span>ch</span> <span>=</span> <span>(</span><span>s</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>)-</span><span>'a'</span><span>)</span> <span>+</span><span>1</span><span>;</span>

            <span>prefix</span> <span>=</span> <span>(</span><span>int</span><span>)((</span><span>1L</span> <span>*</span> <span>prefix</span> <span>*</span> <span>base</span><span>)</span> <span>%</span> <span>mod</span><span>);</span>
            <span>prefix</span> <span>=</span> <span>(</span><span>int</span><span>)((</span><span>prefix</span> <span>+</span> <span>ch</span><span>)</span> <span>%</span> <span>mod</span><span>);</span>

            <span>suffix</span> <span>=</span> <span>(</span><span>int</span><span>)((</span><span>suffix</span> <span>+</span> <span>1L</span> <span>*</span> <span>ch</span> <span>*</span> <span>power</span><span>)</span> <span>%</span> <span>mod</span><span>);</span>
            <span>power</span> <span>=</span> <span>(</span><span>int</span><span>)((</span><span>1L</span> <span>*</span> <span>power</span> <span>*</span> <span>base</span><span>)</span> <span>%</span> <span>mod</span><span>);</span>
            <span>if</span><span>(</span><span>prefix</span> <span>==</span> <span>suffix</span><span>){</span>
                <span>lastIndex</span> <span>=</span><span>i</span><span>;</span>
            <span>}</span>
        <span>}</span>
        <span>str</span> <span>=</span> <span>s</span><span>.</span><span>substring</span><span>(</span><span>lastIndex</span><span>+</span><span>1</span><span>);</span>
        <span>return</span> <span>new</span> <span>StringBuilder</span><span>(</span><span>str</span><span>).</span><span>reverse</span><span>().</span><span>toString</span><span>()+</span><span>s</span><span>;</span>
    <span>}</span>
<span>}</span>
// using rabin karp hashing approach

class Solution {
    public String shortestPalindrome(String s) {
        int prefix = 0;
        int suffix = 0;
        int lastIndex =-1;
        int base = 29;
        int power = 1;
        int mod = (int)(1e9 + 7);
        String str = "";
        for(int i =0;i<s.length();i++){
            int ch = (s.charAt(i)-'a') +1;

            prefix = (int)((1L * prefix * base) % mod);
            prefix = (int)((prefix + ch) % mod);

            suffix = (int)((suffix + 1L * ch * power) % mod);
            power = (int)((1L * power * base) % mod);
            if(prefix == suffix){
                lastIndex =i;
            }
        }
        str = s.substring(lastIndex+1);
        return new StringBuilder(str).reverse().toString()+s;
    }
}

Enter fullscreen mode Exit fullscreen mode

Important algorithms (3 Part Series)

1 Kadane’s Algorithm
2 Knuth Morris Prat algorithm[Pattern Matching]
3 Rabin Karp (hashing) String pattern matching

原文链接：Rabin Karp (hashing) String pattern matching