比较两个唯一字符串时如何检测模式匹配？

Question

我正在寻找以下字符串模式匹配问题的解决方案。

您有一个带有两个参数的函数：模式和输入 - 都是字符串。

假设 pattern: aabbaa 和 input: catcatdogdogcatcat

这些特定参数将被视为匹配项，因为 input 的字符中存在一个模式，并且该模式与 pattern

中的单词模式相匹配

Return a boolean 表示是否匹配。上面给出的示例将 return 1.

function (pattern, input) {
  // patterns within the input string are elucidated from input
  // those patterns are checked against the pattern
  return boolean
}

Answer 1

创建一个嵌套循环来检查。

int i =0;
char tester [] = "xyzfffasdfsadf";
bool checker = false;
while (tester[i] != '[=10=]')
{
    if (tester [i] == 'x')
    {
        i++;
       if (tester[i] == 'y')
       {
          i++;
          if (tester[i] == 'z')
          {
             checker = true;
          }
       }
   }else {
    i++;
   }
}
if(checker == true){
cout << "Pattern exist";
}

这是c++或java中的一种简单方法，我会这么认为。嵌套循环的数量将是要检查模式是否存在的字符数。您还可以在最后一个循环中包括第二个计数器以递增以计算模式出现的次数。

Answer 2

广义问题 "Find the patterns for a given string" 更难解决，因为一个字符串可以符合多种模式。例如，

catcatdogcat

符合多种模式。这是一个非详尽的列表：

aaba           cat cat dog cat
a              catcatdogcat
ab             catcat dogcat
abcabcefgabc   c a t c a t d o g c a t
ababcab        ca t ca t dog ca t

所以我认为 "find all patterns, then see if the proposed pattern is among them" 的方法行不通。

这意味着我们可能希望使用建议的模式作为尝试分解字符串的指南，但我也不完全确定它看起来如何。

在模式以相同子字符串开始和结束的特定情况下（例如在 aaba 中），我想您可以从字符串的开头和结尾开始，一次消耗一个字符直到你找到匹配项：

catcatdogcat
CatcatdogcaT
CAtcatdogcAT
CATcatdogCAT <-- Substring "CAT" is a candidate for "a". Check if that pattern matches.

但更一般的情况又更难了。但是，可以采用类似的方法，例如尝试每个字符串以查看它是否符合模式，并进行回溯：

catcatdogcat
Catcatdogcat <-- The string isn't "CCsomethingC", so a != "C"
CAtcatdogcat <-- the string isn't "CACAsomethingCA", so a != "CA"
CATcatdogcat <-- the string is "CATCATsomethingCAT", so a = "CAT" is a candidate.

一旦找到候选项，就可以将其从字符串和模式字符串中删除，从而减少下一步，将 dog 与模式 b 进行比较。在伪代码中，

checkpattern(pattern, string) :=
  if (pattern has just one letter) 
    return true
  if (pattern has more than one letter, but it's one character repeated)
    return whether the string repeats that way
  for (each substring from the start of the string of length x=[0..])
    does the string match this candidate substring following the pattern?
    if (yes)
      if (checkpattern(pattern - letter, string - substring))
        return true
      else
        continue
    if (no)
      continue
  return false

我想那行得通。显然这个伪代码有很多细节，它不是很有效，但它会完成工作。

Answer 3

这是我的做法

def check_pattern(s1,s2):
    i=j=97
    p1=p2=""

    for index1,l1 in enumerate(s1):
        if l1 not in s1[0:index1]:
            p1+=chr(i)
            i+=1
        else:
            p1+= chr(97+s1.index(l1))

    
    for index2,l2 in enumerate(s2):
        if l2 not in s2[0:index2]:
            p2+=chr(j)
            j+=1
        else:
            p2+= chr(97+s2.index(l2))

    if p1==p2:
        return True
    else:
        return False

z=check_pattern("aab","xxz")
print(z)

比较两个唯一字符串时如何检测模式匹配？

How do you detect a pattern match when comparing two unique strings?

string

algorithm

pattern-matching

automaton

rabin-karp