标签: string-matching

这是"算法设计和分析导论"中的练习.这是一个字符串匹配问题.假设我有字符串ABCD,并且有一个模式XY.并希望查看字符串是否包含模式.

我们假设在这里使用蛮力,所以从左到右的比较是将A与X进行比较,接下来是将B与X进行比较等.而从右到左的比较是将B与Y进行比较,接下来是比较C与B.暗示说从右到左的比较确实有优势,但我不明白为什么.

任何提示都很感激!

可能重复:
Javascript:从字符串中删除非数字字符

字符串匹配对我来说很头疼.

例:

如果我有这样的字符串:

abc123xyz456()*
^%$111u222

然后将其转换为:

123456
111222

我正在尝试理解aho-corasick字符串匹配算法.假设我们的模式是abcd和bc.我们最终得到了这样一棵树

       []
       /\
    [a]..[b]
    /  :  |
   [b].: [c]
    |     :
   [c].....
    |
   [d]

虚线表示故障功能.

现在假设我们输入字符串abcd.这将跟随树并检测匹配"abcd",但是,据我所知,匹配bc将不会被报告.我误解了算法吗？

在Data/ByteString.hs它的来源中说该函数findSubstrings已被弃用而有利于breakSubstring.但是我认为findSubstrings使用KMP算法实现的算法比使用的算法更有效率breakSubstring.任何人都知道为什么要这样做？

这是旧的实现:

{-# DEPRECATED findSubstrings "findSubstrings is deprecated in favour of breakSubstring." #-}

{-
{- This function uses the Knuth-Morris-Pratt string matching algorithm.  -}

findSubstrings pat@(PS _ _ m) str@(PS _ _ n) = search 0 0
where
  patc x = pat `unsafeIndex` x
  strc x = str `unsafeIndex` x

  -- maybe we should make kmpNext a UArray before using it in search?
  kmpNext = listArray (0,m) (-1:kmpNextL pat (-1)) …

我有一个格式如下的字符串:

"key1=value1;key2=value2;key3=value3"

对于任意数量的键/值对.

我需要检查某个键是否存在(假设它叫做"特殊键").如果是,我想要与之相关的值.如果有多个"特殊键"设置,我只想要第一个.

现在,我正在寻找"特殊键"的索引.我从该索引处开始一个子串,然后查找第一个=字符的索引.然后我寻找第一个;字符的索引.这两个索引之间的子字符串给出了与"特殊键"相关的值.

这不是一个优雅的解决方案,它真的很困扰我.找到与"特殊键"对应的值的优雅方法是什么？

假设我的程序收到一个输入,例如一串具有任何类型字符的字符.例如,'Bob's Bagel Shop'.然后它得到另一个字符串,上面写着'Fred's Bagel Store'.如何在python中使用正则表达式或其他模块来比较这些并让我的程序告诉我,如果字符串中的任何字符串中的至少5个(或任何我想要的数字)是相同的,但是所有字符都在相同的顺序中,比如'Bagel'这个词？

谢谢.

我有数据的地方如下

 location<- c("xyz, sss, New Zealand", "USA", "Pris,France")
 id<- c(1,2,3)
 df<-data.frame(location,id)

我想从数据中提取国家/地区名称.棘手的部分是,如果我只提取最后一个单词,那么我将只有一个记录(法国).

library(stringr)
df$country<- word(df$location,-1)

关于如何从这些数据中提取国家数据的任何想法？

 id  location                      country
  1   xyz, sss, New Zealand        New Zealand
  2   USA                          USA
  3   Pris,France                  France

我有一个问题，我们可以用ed值除以两个字符串的长度来归一化levenshtein编辑距离吗？我之所以这样问是因为，如果我们比较两个长度不相等的字符串，那么两个长度之间的差异也将被计算在内。例如：ed（'has a'，'has a ball'）= 4，而ed（'has a'，'has a ball the round'）=15。如果我们增加字符串的长度，则编辑距离即使它们相似，也会增加。因此，我无法设置一个值，好的编辑距离值应该是多少。

如何使用 RegEx 来测试以下模式：

1. 字符串长度必须为 4-10 个字符
2. 字符串不得有任何重复字符（两个字符不能相同且相邻）

我对此进行了研究，我认为我很接近：

^(?!(.)\1).{4,10}$

ab12这将正确找到和的匹配项12ab。它还正确地拒绝1111和aaaa。然而它错误地接受了12aa和ab11。

它似乎只查找字符串开头的重复字符。我尝试移动或删除^和$，但我需要它们来进行最大字符检查。我还尝试了几种变体(.)\1来查找重复字符，但没有成功。

任何帮助或提示将不胜感激。

PS - 如果有人知道答案，我实际上希望最多允许一对重复字符，但我认为这太难了，并决定禁止任何重复字符。

我正在尝试创建某种字典来附加我的结果并使用 jaro 距离函数获得最佳匹配。

这是我尝试匹配两个列表并在两个列表中获得最佳匹配名称的一部分。

例子：

import jellyfish
jellyfish.jaro_distance(u'jellyfish', u'sellyfish')

output: 
0.9259259259259259

我想做的是：

listA = ['grellofish','mellofush','jellyfihs','sellyfish','salmonfish']
listB = ['jellyfish','salmonfish']

#convert to unicode
listA = [unicode(i) for i in listA]
listB = [unicode(i) for i in listB]

for nickB in listB:
    for nickA in listA:
        results = jellyfish.jaro_distance(nickA, nickB)
        print nickB,nickA,results

output:
jellyfish grellofish 0.825925925926
jellyfish mellofush 0.777777777778
jellyfish jellyfihs 0.962962962963
jellyfish sellyfish 0.925925925926
jellyfish salmonfish 0.685185185185
salmonfish grellofish 0.733333333333
salmonfish mellofush 0.7
salmonfish jellyfihs 0.618518518519
salmonfish sellyfish 0.755555555556
salmonfish salmonfish 1.0 …