流中回文檢查的在線算法  


難度級別 中烘焙
經常問 ol石 土磚 Zenefits
回文 模式搜索

問題陳述  

在“檢查流中回文率的在線算法”問題中,我們給出了一個字符流(字符被一個接一個地接收)。 編寫一個程序,如果到現在為止收到的字符都形成一個字母,則每次都會打印“ yes” 回文.

輸入格式  

第一行也是只有一行包含 s.

輸出格式  

如果當前字符串(直到此字符為止由所有字符組成)是回文,則逐字符遍歷並打印“是”,否則打印“否”。

約束  

  • 1 <= | s | <= 10 ^ 5
  • s [i]必須為小寫英文字母

例  

bcdcb
YES  
NO 
NO 
NO   
YES

說明: 對於i = 0,打印“是”,因為“ b”是回文。 如果i = 1,則打印NO,因為“ bc”不是回文。 對於i = 2,請打印NO,因為“ bcd”不是回文。 如果i = 3,則打印“否”,因為“ bcdc”不是回文。 對於i = 4,請打印YES,因為“ bcdcb”是回文。

流中回文校驗的在線算法  

基本思想是,對於輸入字符串中的每個字符,請檢查s [0..i]是否為回文。 在另一種方法(最佳)中,主要思想是使用Rabin Karp算法中使用的Rolling hash的思想,因為可以根據O(1)時間中的前一個值來計算下一個哈希值。 跟踪每個索引的上半年和下半年的反向

也可以看看
查找最近的回文數

算法  

1. 第一個字符始終是回文,因此請為第一個字符打印是。

2. 初始化前半部分到第一個字符的反轉,後半部分到第二個字符的反轉。 假設上半部分的哈希值取反為“ FR”,而下半部分的哈希值取為“ S”。

3. 從第二個字符開始遍歷字符串

  • 如果“ FR”和“ S”相同,則檢查iff s [0..i]是否為回文,使用簡單的字符逐字符匹配
  • 更新“ FR”和“ S”以進行下一次迭代。
  • 如果“ i”是偶數,則將下一個字符添加到“ FR”的開頭和下半部分的結尾,並更新哈希值。
  • 如果“ i”是奇數,則保持“ FR”不變,從第二個字符中刪除前導字符,並在末尾附加下一個字符。

以上算法的工作實現

s =“ bcdcb”
初始化FR和S。FR =哈希(“ b”),S =哈希(“ c”)
從第二個字符開始遍歷
i = 1,FR和S不相等,因此打印NO。
更新FR和S,i為奇數,因此FR將不會更改,並且S變為hash(“ d”)
i = 2,FR和S不相等,因此打印NO。
更新FR和S,i甚至是FR,因此FR變為hash(“ cb”),而S變為hash(“ dc”)
i = 3,FR和S不相等,因此打印NO。
更新FR和S,i為奇數,因此FR將不會更改,並且S變為hash(“ cb”)
i = 4,FR和S匹配,所以打印YES。
無需更新,因為它是最後一個索引

履行  

用於檢查流中回文的在線算法的C ++程序

#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
// p is a prime number used for evaluating Rabin Karp's Rolling hash
#define p 103
 
void isPalindrome(string s)
{
    // Length of input string
    int N = s.length();
 
    // first character is a palindrome
    cout<<"YES"<<endl;
 
    // Return if string has only one character
    if (N == 1) return;
 
    // Initialize first half reverse and S half for 
    // as FR and S characters
    int FR  = s[0] % p;
    int S = s[1] % p;
 
    int h = 1, i, j;
 
    // Now check for palindromes from S character
    // onward
    for (i=1; i<N; i++)
    {
        // If the hash values of 'FR' and 'S' 
        // match, then only check individual characters
        if (FR == S)
        {
            //check if s[0..i] is a palindorme
            for (j = 0; j < i/2; j++)
            {
                if (s[j] != s[i-j])
                    break;
            }
            if((j == i/2))
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        else
        { 
            cout<<"NO"<<endl;
        }

        //update hash values
        if (i != N-1)
        {
            // If i is even (next i is odd) 
            if (i%2 == 0)
            {
                // Add next character after first half at beginning 
                // of 'FR'
                h = (h*NO_OF_CHARS) % p;
                FR  = (FR + h*s[i/2])%p;
                 
                // Add next character after S half at the end
                // of S half.
                S = (S*NO_OF_CHARS + s[i+1])%p;
            }
            else
            {
                // If i is odd (next i is even) then we
                // need not update FR, we need to remove
                // first character of S and append a
                // character to it.
                S = (NO_OF_CHARS*(S + p - s[(i+1)/2]*h)%p
                          + s[i+1])%p;
            }
        }
    }
}
 
int main()
{
    string s;
    cin>>s;
    isPalindrome(s);
    return 0;
}

用於檢查流中回文的在線算法的Java程序

import java.util.Scanner;
class sum
{
    private static int p=103;
    private static int NO_OF_CHARS = 256;
    public static void isPalindrome(String s)
    {
        // Length of input string
        int N = s.length();

        // first character is a palindrome
        System.out.println("YES");

        // Return if string has only one character
        if (N == 1) return;

        // Initialize first half reverse and S half for 
        // as FR and S characters
        int FR  = s.charAt(0) % p;
        int S = s.charAt(1) % p;

        int h = 1, i, j;

        // Now check for palindromes from S character
        // onward
        for (i=1; i<N; i++)
        {
            // If the hash values of 'FR' and 'S' 
            // match, then only check individual characters
            if (FR == S)
            {
                //check if s[0..i] is a palindorme
                for (j = 0; j < i/2; j++)
                {
                    if (s.charAt(j) != s.charAt(i-j))
                        break;
                }
                if((j == i/2))
                {
                    System.out.println("YES");
                }
                else
                {
                    System.out.println("NO");
                }
            }
            else
            { 
                System.out.println("NO");
            }

            //update hash values
            if (i != N-1)
            {
                // If i is even (next i is odd) 
                if (i%2 == 0)
                {
                    // Add next character after first half at beginning 
                    // of 'FR'
                    h = (h*NO_OF_CHARS) % p;
                    FR  = (FR + h*s.charAt(i/2))%p;

                    // Add next character after S half at the end
                    // of S half.
                    S = (S*NO_OF_CHARS + s.charAt(i+1))%p;
                }
                else
                {
                    // If i is odd (next i is even) then we
                    // need not update FR, we need to remove
                    // first character of S and append a
                    // character to it.
                    S = (NO_OF_CHARS*(S + p - s.charAt((i+1)/2)*h)%p
                              + s.charAt(i+1))%p;
                }
            }
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        isPalindrome(s);
    }
    
}
abacbca
YES
NO
YES
NO
NO
NO
NO

流中回文檢查在線算法的複雜度分析  

時間複雜度

O(n * n) 哪裡 n 是給定字符串的大小。 這裡n * n是最壞情況下的時間複雜度。 但總的來說,它比基本的簡單方法要好得多。 由於我們大多數時候會通過首先比較散列值來避免完整的子字符串比較。 最壞的情況發生在具有所有相同字符(例如“ zzzzzzzzzzz”)的輸入字符串中。

也可以看看
包含通配符的字符串比較

空間複雜度

O(1) 因為我們在這裡沒有任何輔助空間。