python實現公共子串

㈠ 459. 重復子字元串（python）

難度：★☆☆☆☆
類型：數組

給定一個非空的字元串，判斷它是否可以由它的一個子串重復多次構成。給定的字元串只含有小寫英文字母，並且長度不超過10000。

示例 1:
輸入: "abab"
輸出: True
解釋: 可由子字元串 "ab" 重復兩次構成。

示例 2:
輸入: "aba"
輸出: False

示例 3:
輸入: "abcabcabcabc"
輸出: True
解釋: 可由子字元串 "abc" 重復四次構成。 (或者子字元串 "abcabc" 重復兩次構成。)

這里我們觀察到一個現象，對於一個字元串s，我們將兩個該字元串連接成一個更長的字元串（s_double），該字元串中至少包含兩個s子串，如果s可以由多個重復單元構成，那麼合並後的字元串中一定包含超過兩個s子串（可重疊），例如，兩個"abab"組成的"abababab"中包含3個"abab"，而兩個"aba"組成的"abaaba"則只包含兩個"aba"，根據這個原理，我們只需要統計s+s中s（可重疊）出現的次數，並與2比較即可。

這里為了簡化計算，我們把s+s的首尾兩端字元去掉，這樣就只需要查看s是否在剩餘的字元串中即可。編碼時通過索引范圍[1:len(s)*2-1]起到去掉首尾兩端字元的效果。

如有疑問或建議，歡迎評論區留言~

㈡ Python字元串split及rsplit方法原理詳解

1.描述

split()方法通過指定分隔符對字元串進行切片，如果參數num有指定值，則分隔num+1個子字元串，默認分隔符為所有空字元，包括空格、換行(\n)、製表符(\t)等

rstrip()方法通過

2.語法

str.split([sep=None][,count=S.count(sep)])

str.rsplit([sep=None][,count=S.count(sep)])

3.參數

sep -- 可選參數，指定的分隔符，默認為所有的空字元，包括空格、換行(\n)、製表符(\t)等

count -- 可選參數，分割次數，默認為分隔符在字元串中出現的總次數

4.返回值

返回分割後的字元串列表，可以用新字元串來接收

5.實例

str1 = "Hao123 hao456 hAo789"

new_str = str1.split()

new_str2 = str1.split(' ', 1)

new_str3 = str1.rsplit(' ', 1)

print(new_str)

print(new_str2)

print(new_str3)

#輸出結果如下：

['Hao123', 'hao456', 'hAo789']

['Hao123', 'hao456 hAo789']

['Hao123 hao456', 'hAo789']

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持。

㈢ Python 標准庫模塊 - re

正則表達式引擎對正則表達式文本進行編譯生成正則表達式對象，再由正則表達式對象對目標文本進行匹配，後返回匹配結果。

正則表達式中一共包含 2 中字元： 普通字元 、 元字元

匹配單個字元的元字元及其含義：

匹配重復性的元字元及其含義：

匹配位置的元字元及其含義：

分組匹配的元字元及其含義：

表示或運算的元字元：

轉義元字元：

在 Python 中使用正則表達式，我們需要藉助 re 模塊提供的強大 API，下面我們就來學習幾個 re 模塊常用的介面吧~

參數說明： findall("正則表達式", "要匹配的字元串", flags=標志1|標志2|...)
返回值：以列表形式返回匹配到的字元串。

下面，我們用 findall 返回 Python 之禪中首尾用到的反義詞：

運行結果：

當正則表達式中含有一個以上分組時， findall 返回的列表由元組構成，元組中包含每個分組匹配到的內容。如果只有一個分組，則返回由該分組匹配到的內容組所構成的列表：

match 函數返回的結果是一個 SRE_Match 對象：

SRE_Match 具有很多的屬性，比如 .string 屬性可以方便我們我獲取在匹配時輸入的字元串：

屬性 .re 可以獲取匹配時使用的編譯後的正則表達式模式：

由於默認使用了 re.UNICODE ，所以我們這里的 w 可以匹配中文字元。

屬性 .regs 則以列表的形式返回正則表達式匹配到的內容以及各個分組陪陪到的內容，不過請注意，返回的都是索引的形式：

可以使用序列切片來看一下我們的正則表達式及其中的兩個分組所匹配到的內容：

SRE_Match 對象也提供了非常多好用的方法，比如 groups 可以獲取各個分組匹配到的內容：

group 則可以靈活地獲取正則表達式或對應分組匹配到的內容：

如果使用的正則表達式定義了分組的名稱， group 還可以通過名稱獲取相應分組匹配的內容：

在定義了分組的名稱之後，還可以方便地使用 groupdict 以字典的形式返回所有分組匹配的結果：

最後需要注意的是， match 從字元串的開頭開始匹配，如果開頭不符合要求，則直接返回 None 。

與 match 匹配開頭不同， search 匹配第一個符合規則的字元串，未成功則返回 None 。參數： re.search(pattern, string, flags=0) ；返回值同 match 。

在介紹 match 的使用時，最後一個例子，由於我們在字元串前面添加了 'PYTHON' 導致 match 使用原來的正則表達式無法匹配，返回 None 。此時，使用 search 就可以迎刃而解啦：

運行結果：

小結：

參數： re.split(pattern, string, maxsplit=0, flags=0) ， split 功能非常強大，以正則表達式匹配到的標志來分隔字元串，比如下面這樣一個混亂的字元串，我們要提取其中所有的數字：

下面，我們就來詳細介紹一下 split 的用法。

首先，是以單字元切割：

以分號切割時，共產生了 4 個子字元串，放在列表中返回。
下面，還是以單字元切割，但可以使用正則表達式中的 [] 來指定多種字元：

由於字元串 line 中有連續的 2 個分號，逗號或者空格，因此可以使用 [;s,]+ 來切割：

最後，上面的字元串在切割時，分隔符都沒有被保留下來，使用括弧捕獲分組，即可保留分隔符：

re.sub 提供比字元串的 replace 方法更加強大的功能：對於輸入的字元串 string ,利用正則表達式 pattern 強大的字元串處理功能，實現復雜的字元串替換處理為 repl ，返回被替換後的字元串。

下面的例子中，我們將句子中多餘的空格和數字去掉：

如果想要知道替換過程中，共發生了多少次替換，可以使用 subn ：

小結：

上述的案例中，我們每次都需要傳入正則表達式，相應的函數每次在調用時，都需要編譯一次正則表達式。如果上述過程需要多次重復，那麼每次都去耗費時間編譯正則表達式是很不劃算的。

re 模塊為我們提供了 compile 函數，用來編譯正則表達式模式，返回編譯好模式。因此，可以把那些常用的正則表達式編譯成正則表達式對象，以提高效率。

格式： re.compile(pattern, flags=0) ，其中 pattern 為編譯時用的表達式字元串， flags 為編譯標志位，用於修改正則表達式的匹配方式，如：是否區分大小寫，多行匹配等。常用的 flags 有：

註：使用按位或 | 連接多個 flags 。

我們上述介紹的 re 模塊的匹配、分割、替換函數， compile 函數的返回值類提供了相應的方法，使用方式類似，只是不需要傳入正則表達式字元串而已。

由於用法幾乎一致，這里就不一一舉例啦~

貪婪模式 ： * + ? {m,n} ，正則表達式的重復默認總是盡可能多得向後匹配內容。

非貪婪模式 ： *? +? ?? {m,n}? ，盡可能少的匹配內容。

㈣ Python字元串是什麼，如何使用

字元串的表示

字元串可以被成對的單引號(single quote)或雙引號(double quotes)包圍起來，這兩者的作用是一樣的：

更多關於Python的基礎性知識可以看下這個網頁的視頻教程，Python常見的數據類型及使用方法掌握，希望我的回答能幫到你。

㈤ 【python】求兩個字元串的公共字串

題目：找出兩個字元串的最長公共字串，例如字元串「abccade」與字元串「dgcadde」的最長公共子串為「cad」。

分析：動態規劃法。通過把中間的比較結果記錄下來，從而可以避免字元的重復比較。：

首先定義二元函數（i，j）：表示分別以s1[i],s2[j]結尾的公共子串的長度，顯然，f（0， j） = 0 (j >= 0),f(i, 0) = 0(i >= 0),那麼對於f(i +1, j + 1)而言，則有如下兩種取值：
（1) f(i + 1, j +1) = 0,當str1[i + 1] != str2[j + 1]時

（2）f(i + 1, j +1) = f(i, j) + 1,當str1[i + 1] == str2[j + 1]時

根據這個公式可以計算出f(i, j)（0<= i<=len(s1), 0 <= j <= len(s2)，所有的值，從而可以找出最長的子串。

def getMaxSubStr(str1, str2):

    len1 = len(str1)

    len2 = len(str2)

    sb = ''

    maxs = 0  # 用來記錄最長公共子串的長度

    maxI = 0  # 用來記錄最長公共字串最後一個字元的位置

    # 申請新的空間來記錄公共字串長度信息

    M = [([None] * (len1 + 1)) for i in range(len2 + 1)]

    i = 0

    while i < len1 + 1:

        M[i][0] = 0

        i += 1

    j = 0

    while j < len2 + 1:

        M[0][j] = 0

        j += 1

    # 通過利用遞歸公式填寫新建得二維數組（公共字串得長度信息）

    i = 1

    while i < len1 + 1:

        j = 1

        while j < len2 + 1:

            if list(str1)[i - 1] == list(str2)[j - 1]:

                M[i][j] = M[i - 1][j - 1] + 1

                if M[i][j] > maxs:

                    maxs = M[i][j]

                    maxI = i

            else:

                M[i][j] = 0

            j += 1

        i += 1

    i = maxI - maxs

    while i < maxI:

        sb = sb + list(str1)[i]

        i += 1

    return sb

if __name__ == "__main__":

    str1 = 'abccade'

    str2 = 'dgcadde'

    print(getMaxSubStr(str1, str2))

程序運行結果：

cad

㈥ python判斷字元串（string）是否包含（contains）子字元串的方法的代碼

下邊內容是關於python判斷字元串（string）是否包含（contains）子字元串的方法的內容。

方法2：使用find函數實現contains的功能

s = "This be a string"

if s.find("is") == -1:

    print "No 'is' here!"

else:

    print "Found 'is' in the string."

㈦ Python包之OS

參考： https://docs.python.org/3/library/os.html

Python中對OS模塊的定位是：提供了使用操作系統的工具介面。
如果你想讀寫文件，可以參考open()；
如果你想操作文件路徑，參考os.path模塊；
如果你想在命令行讀取所有文件的所有行，參考fileinput模塊；
如果你想創建臨時文件或目錄，參考tempfile模塊；
如果你想更高級的文件和路徑處理，參考shutil模塊；

內置的OSError異常類型，比如在使用os模塊中的函數介面時，在參數中提供了無效的文件或路徑，就回報錯os.error。

該變數返回當前操作系統的類型，當前只注冊了3個值：分別是posix , nt , java， 對應linux/windows/java虛擬機。

在Python中，文件名，命令行參數和環境變數都是用字元串類型來表示。

接下來的這些函數和數據提供了當前進程和用戶的信息狀態和操作介面。

返回進程式控制制終端的文件名，適用於Unix系統。

返回字元串到環境變數的映射。

改變當前工作目錄到指定的路徑，path為要切換到的新路徑。

通過文件描述符改變當前工作目錄。
文件描述符是內核為了高效管理已經被打開的文件所創建的索引，

進程通過文件描述符來訪問文件。 在程序剛啟動的時候默認有3個文件描述符：0(標准輸入)，1(標准輸出)，2(標准錯誤)，系統默認提供了 0～2的文件描述符，之後的 當我們進行 open,create等操作的時候 自動添加進表

所以int creat(const char * ,mode_t)返回的文件int 就是你所進行操作的文件的唯一身份標示，

然後你只要拿著這個ID 然後告訴系統給我找xx， write(int fd,char *buf,int lenght) 通過fd得到准確文件 然後寫入。

當我們新建creat，打開open 之後，得到的fd 是從3開始的 因為前面的三個被系統佔了在OS X系統下測試 文件描述符表 自增，當釋放close之後，fd變成－1，如果再繼續新建 則填補之前的空缺。

返回當前工作目錄。

把字元串類型的文件名翻譯成bytes類型的文件名；os.fsdecode()實現相反的功能。

返迴路徑的文件系統表示。

如果環境變數中存在key，返回環境變數key的值，否則返回default的值。

設置環境變數key的值為value。

使用當前uid/gid檢測對路徑path是否有訪問許可權。其中，path為要檢測是否有許可權的路徑，mode為許可權類別，值可以為os.F_OK、os.R_OK、os.W_OK、os.X_OK中的一個或多個；

切換當前的工作路徑為path指定的路徑。

設置路徑path的標記為flags，flags為數字標記，多個flags可以使用or組合。flags可以為以下值或以下值的組合：

更改文件或目錄的許可權。
path -- 文件名路徑或目錄路徑
mode -- 可用以下選項按位或操作生成， 目錄的讀許可權表示可以獲取目錄里文件名列表， 寫許可權表示可以獲取文件並且可以修改內容，執行許可權表示可以把工作目錄切換到此目錄 ，刪除添加目錄里的文件必須同時有寫和執行許可權 ，文件許可權以用戶id->組id->其它順序檢驗,最先匹配的允許或禁止許可權被應用。

更改路徑的擁有者和group id為uid和gid。如果不修改可以設置為-1，並且需要超級用戶許可權來執行許可權修改操作。
path -- 設置許可權的文件路徑
uid -- 所屬用戶ID
gid -- 所屬用戶組ID

更改當前進程的根目錄為path。

返回當前工作目錄。

返回path目錄路徑下的文件列表，列表沒有固定的順序。

創建目錄path。如果目錄已經存在，會拋出異常FileExistsError。

遞歸的目錄創建，遞歸的意思是創建所有到達葉子目錄的中間目錄。

從原始設備號（通常是stat中的st_dev或st_rdev）中提取設備major號碼。

從原始設備號（通常是stat中的st_dev或st_rdev）中提取設備minor號碼。

根據設備的major號碼和minor號碼組成原始設備號。

刪除文件路徑path。如果path指向的是目錄路徑，會拋出異常IsADirectoryError。如果要刪除目錄，使用rmdir。

遞歸的刪除目錄。與rmdir功能相似，不同的是，如果葉子目錄被刪除之後，removedirs會連續的刪除每一層上級目錄，直到拋出異常（異常會被忽略，因為異常通常意味著上層目錄為非空目錄）。

重命名文件或路徑src為dst，如果dst已經存在，會拋出異常。

遞歸的重命名文件或目錄。功能與rename類似，不同在於，renames首先創建new路徑（即重命名之後的路徑）的中間路徑，然後創建完整new路徑，最後，會使用removedirs刪除掉old路徑（實際上刪除的是old路徑與new路徑不重合的部分）。

重命名文件或路徑src為dst。如果dst是目錄，拋出異常OSError。如果dst是文件且已經存在，且用戶具有許可權，dst會被替換掉。

刪除path目錄。如果path不存在，或者path非空，會拋出異常FileNotFoundError或OSError。如果要刪除整個目錄樹，可以使用shutil.rmtree()。

返回path的絕對路徑，效果等同於使用normpath：normpath(join(os.getcwd(), path))。

返迴路徑path的文件名，也就是對path調用os.path.split函數返回的元組的第二個元素。

paths為一個序列類型，其中每個元素表示一個路徑，函數返回結果為每個元素所表示的路徑的最長公共子路徑。如果paths為空，或者paths同時包含絕對路徑和相對路徑，或者paths同時包含不同驅動類型的路徑（比如Linux系統的路徑和Windows系統的路徑），則拋出異常ValueError。

list中的每個元素表示一個路徑，函數返回每個路徑的最長的共有路徑前綴，因為計算方式為逐個字元進行比較，所以可能返回的結果並非有效的路徑，如果要返回有效路徑，可以使用commonpath。

返回path路徑的目錄部分，也就是對path調用os.path.split函數返回的元組的第一個元素。

如果path指向的路徑已存在，則返回True，否則返回False。

在Unix和Windows系統中，返回path路徑中的~被替換成用戶的home目錄之後的結果。

path路徑中的 {name}被環境變數中對應名稱的值替代。

返回最後一次訪問path的時間，返回值的格式為一個float類型的數值，表示距離epoch基準時間1970-01-01 00：00：00的秒數。如果path表示的路徑不存在或者沒有許可權，拋出異常OSError。

返回最後一次修改path的時間，返回值的格式為一個float類型的數值，表示距離epoch基準時間1970-01-01 00：00：00的秒數。如果path表示的路徑不存在或者沒有許可權，拋出異常OSError。

返回path表示的文件或路徑的大小，以byte位元組為單位。如果path表示的路徑不存在或者沒有許可權，拋出異常OSError。

如果path是絕對路徑，返回True，否則返回False。

如果path表示的是已存在的文件路徑，返回True。

如果path表示的是已存在的目錄，返回True。

如果path表示的是鏈接，返回True。

判斷path是否為掛載點。

連接一個或多個路徑，path和多個*paths的連接會使用路徑分隔符。

對path的字母大小寫進行normalize。在Windows系統中，path中的所有字母都轉成小寫，並且把正斜杠轉成反斜杠。在其他操作系統中，返回path本身。

對path進行normalize，刪除多餘的路徑分隔符。

split the path into a pair (head, tail)，其中tail是path中最後的部分，並且永遠不會含有斜杠，head是除了tail之外的部分。如果path以斜杠結尾，tail為空；如果path中不包含斜杠，head為空；如果path為空，head和tail都是空。

㈧ 兩個字元串的最長公共子串python代碼

最長公共子串（Longest Common Substring）： 是指兩個字元串中最長連續相同的子串長度。
例如：str1=「1AB2345CD」,str2=」12345EF」,則str1，str2的最長公共子串為2345。

㈨ 尋找字元串數組的最長公共子串

所謂最長公共子串問題是尋找兩個或多個已知字元串最長的子串。例如字元串 「ABCD」與「ABCDE」、「FABCDE」的最長公共子串是「ABCD」……

值得注意的是，有些人把最長公共子序列、最長公共前綴與最長公共子串搞混淆了，請特別注意⚠️。

《高效演算法：競賽、應試與提高必修128例》中介紹了最長公共子串的演算法，不過只是找兩個字元串之間的最長公共子串， 並沒有給出任意個數 （此處當然指的是3個或以上）字元串的最長公共子串的求法。

現在用Python試寫如下：

最長子串還可以用lamada寫法，看起來更加簡潔

這個方法的復雜度是 O(n1 x n1 x (n1 + ... + nK)) ， 如果字元串不復雜，還是可以一用的😄。

㈩ Python淺薄的基礎小結上

Python 支持四種不同的數值類型：

整型(Int) - 通常被稱為是整型或整數，是正或負整數，不帶小數點。

長整型(long integers) - 無限大小的整數，整數最後是一個大寫或小寫的L。

浮點型(floating point real values) - 浮點型由整數部分與小數部分組成，浮點型也可以使用科學計數法表示（2.5e2 = 2.5 x 102= 250）

復數(complex numbers) - 復數由實數部分和虛數部分構成，可以用a + bj,或者complex(a,b)表示， 復數的實部a和虛部b都是浮點型。

在Phton中常見的運算加、減、乘、除、求余、冪指數等，同現實生活中的遵循一樣的優先順序。即，乘除運算高於加減運算。例：

Python內置復數的計算支持所有常見復數的計算，對復數處理的數學函數在模塊cmath中：

字元串或串(String)是由數字、字母、下劃線組成的一串字元。Python字元串最大的特點是 不可修改， 只能生成新的字元串，用 雙引號或單引號 都可以表示字元串，多行字元串用三個連續單引號表示，特殊字元用轉義符 「\" 表示如： 製表符"\t",換行符"\n"

>>>str='Hello World!'

>>>print  str*2   # 輸出字元串兩次

Hello World!Hello World!

>>>print  str+"TEST"   # 輸出連接的字元串

Hello World!TEST

>>>len('str')   #輸出字元串的長度

12

python的 字串列表 有2種取值順序:

從左到右索引默認0開始的，最大范圍是字元串長度少1

從右到左索引默認-1開始的，最大范圍是字元串開頭

如果你要實現從字元串中獲取一段子字元串的話，可以使用變數 [頭下標:尾下標] ，就可以截取相應的字元串，其中下標是從 0 開始算起，可以是正數或負數，下標可以為空表示取到頭或尾。比如:

s = 'ilovepython'

s[1:5] 的結果是 love。

當使用以冒號分隔的字元串，python返回一個新的對象，結果包含了以這對偏移標識的連續的內容，左邊的開始是包含了下邊界。

上面的結果包含了s[1]的值l，而取到的最大范圍不包括上邊界，就是s[5]的值p。

'abcd'[3:1:-1]  #從右到左

'dc'

一些高級操作：

>>>s='You are my sunshine'

>>>s.split(' ')

['You' ,'are', 'my' ,'sunshine']

>>>t=['one','for','two']

>>>' '.join(t)

'one for two'

>>>t='Mike and Tom'

>>>t.replace('Tom','jane')

'Mike and jane'

python變數的概念和初中代數的方程變數一致，變數就像貼在東西上的標簽，命名規則：大小寫英文、數字和下劃線，且不能用數字開頭，變數可以反復賦值，而且可以是不同類型的變數

序列是Python中最基本的數據結構。序列中的每個元素都分配一個數字 - 它的位置，或索引，第一個索引是0，第二個索引是1，依此類推。

Python有6個序列的內置類型，但最常見的是列表和元組。

序列都可以進行的操作包括索引，切片，加，乘，檢查成員。

此外，Python已經內置確定序列的長度以及確定最大和最小的元素的方法。

列表 是最常用的Python數據類型，它可以作為一個方括弧內的逗號分隔值出現。

列表的數據項不需要具有相同的類型

創建一個列表，只要把逗號分隔的不同的數據項使用方括弧括起來即可。

>>>[]  #創建空的列表

[]

>>>list() #創建空的列表

[]

>>>alist=['physics','chemistry',1997,2000]

['physics','chemistry',1997,2000]

List（列表） 是 Python 中使用最頻繁的數據類型。

列表可以完成大多數集合類的數據結構實現。它支持字元，數字，字元串甚至可以包含列表（即嵌套）。

列表用[ ]標識，是 python 最通用的復合數據類型。

列表中值的切割也可以用到變數[頭下標:尾下標]，就可以截取相應的列表，從左到右索引默認 0 開始，從右到左索引默認 -1 開始，下標可以為空表示取到頭或尾。

>>>list=['runoob', 786, 2.23, 'john', 70.2]

>>>tinylist=[123, 'john']

>>>print list  # 輸出完整列表

['runoob', 786, 2.23, 'john', 70.2]

>>>'runoob' in alist  #某個元素是否存在

True

>>>print list[0]   # 輸出列表的第一個元素

runoob

>>>print list[1:3]   # 輸出第二個至第三個元素

[786,2.23]

>>>print list[2:]   # 輸出從第三個開始至列表末尾的所有元素

[2.23,'john',70.2]

>>>print tinylist*2   # 輸出列表兩次

[123,'john',123,'john']

>>>print list+tinylist   # 列印組合的列表

['runoob',786,2.23,'john',70.2,123,'john']

Python的元組 與列表類似，不同之處在於元組的元素不能修改。

元組使用小括弧，列表使用方括弧。

元組創建很簡單，只需要在括弧中添加元素，並使用逗號隔開即可。

>>>()  #創建空的元組

()

>>>tuple()  #創建空的元組

()

元組中只包含一個元素時，需要在元素後面添加逗號如：tup1=(50,);

>>>tup=(1,True,0.234,"holle")

同列表相似 元組 適用：

+ ：鏈接兩個元組

* ：復制n次，生成新的元組

in ：某個元素是否存在

[start:end:step] ：切片

值得注意的是元組是不可以更新的（ 不可變） 序列，但我們可以對元組進行連接組合生成新的元組如：

>>>tup1=(12,34.56)

>>>tup2=('abc','xyz')

>>>tup3= tup1+tup2

>>>print tup3

(12,34.56,'abc','xyz')

任意無符號的對象，以逗號隔開，默認為元組。

字典是另一種可變容器模型，且可存儲任意類型對象。

字典的每個鍵值(key=>value)對用冒號( : )分割，每個對之間用逗號( , )分割，整個字典包括在花括弧( {}) 中 ,格式如下所示：

d= {key1:value1,key2:value2}

鍵必須是唯一的，但值則不必。

值可以取任何數據類型，但鍵必須是不可變的，如字元串，數字或元組。

字典是可變類型，可以添加，刪除，替換