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

Question

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

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

比方说

pattern: aabbaa

和

input: catcatdogdogcatcat

这些特定参数将被视为匹配，因为

input

的字符中有一个模式，并且该模式与

pattern

中的单词模式匹配

返回

boolean

来指示是否存在匹配。 上面给出的示例将返回

1

。

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

Answer 1

“查找给定字符串的模式”这一广义问题更难解决，因为一个字符串可以符合多种模式。例如，

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

所以我认为“找到所有模式，然后看看建议的模式是否在其中”的方法行不通。

这意味着我们可能想使用建议的模式作为指导来尝试分解字符串，但我也不完全确定它会是什么样子。

在特定情况下，当模式以相同的子字符串开始和结束时（例如在

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 2

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

int i =0;
char tester [] = "xyzfffasdfsadf";
bool checker = false;
while (tester[i] != '\0')
{
    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 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)

Answer 4

嘿，这是一个非常简单的函数，可用于模式匹配：

    def check_string(str1,str2):
    
        if(len(str1)!=len(str2)):
            return False
        else:
            for i in range(len(str1)):
                for I in range(i+1,len(str1)):
                    if str1[I] == str1[i]:
                        indx1=I
                for J in range(i+1,len(str2)):
                    if str2[J] == str2[i]:
                        indx2=J
                if(indx1!=indx2):
                    return False
        return True
    
   str1 = "catcatcatdogcat" #you can insert any string say abc,xyz  
                            #i used this example
   str2 = "tietietiefortie"
   result = check_string(str1, str2)
   print(result)

说明1：两个字符串的长度必须相同

解释 2：我们可以迭代任一字符串的长度，因为它是相同的

解释 3：我们现在必须检查字符串 1 中第一个字母之后的后续字母，这就是范围从 i+1 开始的原因

解释 4：我们现在检查该字母是否出现在字符串中的其他位置，如果是，我们将此索引存储在 indx1 中

解释 5：我们对第二个字符串也做同样的事情

解释 6：我们现在检查两个字符串的索引是否相同，这是为了检查字母出现的位置是否相同，如果为 false，则返回 False

解释7：遍历完整个字符串后最后返回True，避免第一次返回True

此代码是用Python编写的 我希望这有帮助:)