與多個前綴匹配的字符串

這是一個算法問題;任何僞代碼/口頭解釋都可以做到（儘管Python解決方案大綱將是理想的）。與多個前綴匹配的字符串

讓我們來查詢單詞A，例如pity。而且，我們有一組其他字符串，B S，其中的每一個由一個或多個空格分隔的話：pious teddy，piston tank yard，pesky industrial strength tylenol，oh pity is me!等

的目標是識別這些字符串B從A可以構建爲。這裏的「構造」意味着我們可以以B的順序取前綴一個或多個單詞，並將它們連接在一起得到A。

實施例：

可惜= PI斯通噸 ANK ý ARD
可惜= p ESKY 我 ndustrial強度TY lenol
可惜= OH 可惜是我！

在另一方面，pious teddy不應該被認定，因爲沒有辦法，我們可以採取的話pious和teddy前綴，並將它們連接成pity。

檢查應該很快（理想情況下是一些正則表達式），因爲字符串B的集合可能很大。

來源

2017-05-13 user124114

您可以使用\bp(?:i|\w*(?>\h+\w+)*?\h+i)(?:t|\w*(?>\h+\w+)*?\h+t)(?:y|\w*(?>\h+\w+)*?\h+y)的模式來匹配這些單詞。它假定空格被用作單詞分隔符。這是相當容易構建，只需要匹配您的詞的第一個字母，然後循環其他人，並從他們構建(?:[letter]|\w*(?>\h+\w+)*?\h+[letter])。

此模式基本上是\bp(?:i|.*?\bi)(?:t|.*?\bt)(?:y|.*?\by)的展開版本，它將倒數第二個字母視爲下一個字的下一個字母或第一個字母（由於字邊界）。

你可以看到它在這裏的行動：https://regex101.com/r/r3ZVNE/2

我已經添加了最後一個樣本爲不匹配的一個用於一些測試我的原子團一樣。

在Delphi中我會做這樣的：

program ProjectTest; 

uses 
    System.SysUtils, 
    RegularExpressions; 

procedure CheckSpecialMatches(const Matchword: string; const CheckList: array of string); 
var 
    I: Integer; 
    Pat, C: string; 
    RegEx: TRegEx; 
begin 
    assert(Matchword.Length > 0); 
    Pat := '\b' + Matchword[1]; 
    for I := Low(Matchword) + 1 to High(Matchword) do 
    Pat := Pat + Format('(?:%0:s|\w*(?>\h+\w+)*?\h+%0:s)', [Matchword[I]]); 
    RegEx := TRegEx.Create(Pat, [roCompiled, roIgnoreCase]); 
    for C in CheckList do 
    if Regex.IsMatch(C) then 
     WriteLn(C); 
end; 

const 
    CheckList: array[0..3] of string = (
    'pious teddy', 
    'piston tank yard', 
    'pesky industrial strength tylenol', 
    'prison is ity'); 
    Matchword = 'pity'; 
begin 
    CheckSpecialMatches(Matchword, CheckList); 
    ReadLn; 
end

。

來源

2017-05-13 06:43:19

整潔！「展開」和未展開版本有什麼區別？ '（？：\ h + \ w +）*？\ h + i）'vs'（？：i |。*？\ bi）' – user124114

@ user124114基本上'（？> \ h + \ w +）*？'逐字逐字逐句，而'。*？'逐字逐字地逐字。由於原子組的原因，它還可以減少回溯。 –

與多個前綴匹配的字符串

回答

相關問題