Google面試題 | 循環字元串裡面的獨立子串

03-04

撰文 | Ben助教+ 施助教

專欄 | 九章演算法

題目描述

假設s是一個無限循環的字元串」abcdefghijklmnopqrstuvwxyz」，s就是一個」...zabcdefghijklmnopqrstuvwxyza...」這樣的字元串，現在給你另外一個字元串p，求p中存在多少個截然不同的子串，使得它們也是s的子串。p只包括英語的小寫字母並且p的長度可能大於10000。

樣例說明

輸入：a 輸出：1說明：只有a是s的子串。輸入：cac輸出：2 說明：只有a和c是s的子串。輸入：zab 輸出：6說明：z,a,b,za,ab,zab都是s的子串。

解題思路

1. 這一題我們首先考慮的是，一個長為n的連續的串，有多少個符合題目要求的子串呢？經過思考我們可以得出長為n的連續的串，我們有1+2+3+...+n這麼多個符合題目要求的子串。

2. 解決了上述這個問題，我們直接找出p中所有連續的子串的長度L1,L2,L3...Ln,我們若是直接對(1~L1)(1~L2)...(1~Ln)求和，我們得到的結果顯然是錯誤的，因為會存在字元串重複的問題，例如abcdpjiezabc，這裡abcd和zabc有一部分abc是重複的，我們要求有多少種不同的子串，就需要把這部分重複的減去。如果我們採用暴力計算的方法顯然很麻煩，那麼我們要如何才能避免計算到重複的呢？

3. 在我們學過的數據結構中，有一種數據結構可以避免重複，那就是哈希表！

在本問題中，我們也可以通過哈希表去重。對於一個符合條件的子串（符合條件指的是該串為p的子串），我們只需要記錄「長度」和「結尾字元」這兩個關鍵字就可以唯一確定這個子串。我們以abcdpjiezabc為例，兩個符合條件的極大子串為abcd和zabc，對於abcd，我們把[1,a],[2,b],[3,c],[4,d]記錄到哈希表。細心的讀者可以發現，我們不需要記錄[1,b],[2,c]等等，因為[2,b],[3,c]天然包含了長度比它們小的子串。對於zabc，我們記錄[1,z],[2,a],[3,b][4,c]

4.得到哈希表之後，我們如何統計答案呢？

我們發現，對於[1,a]，因為哈希表中已經存在[2,a]，所以[1,a]所表示的子串已經在[2,a]中被統計。也就是說，為了避免重複統計，我們只需要記錄某個字母結尾的、長度最大的那個符合條件的子串長度就可以了。假設我們的哈希表中對應某個字母P的最長子串長度為k，因為長為k的字元串，有k個子串是以P結尾的，那麼我們需要給最終答案加上k，這種統計方式把所有可能的子串都記錄其中，並且不會重複。綜上我們的演算法時間複雜度為遍曆數組和更新哈希表的時間複雜度：O(N)，空間複雜度為O(1)。

參考代碼

九章演算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時在線授課為你傳授面試技巧

面試官角度

本題考察了字元串的基本操作，以及用哈希表去重的思想，難點在於把最開始的統計方式轉變為以結尾字母為單位的統計方式，算是面試中中等難度的題目。給出正確演算法可以達到hire。

Lintcode 字元串相關題目推薦

LintCode