标签: string-matching

我正在基于Java中的字符串处理创建一个程序,我需要从字符串数组中删除重复的字符串.在此程序中,所有字符串的大小都相同.

作为字符串数组的'array'包含许多字符串,其中两个字符串彼此相似.因此,使用下面的代码必须删除重复的字符串,但不会删除它.

如何删除重复的字符串？

我使用以下代码.

    for(int s=0;s<array.length-1;s++)
    {
        for(int m=0;m<array.length;m++)
        {
                for(int n=0;n<array[m].length();n++)
                {   
                    if(array[s].charAt(n)==array[m].charAt(n))
                    {
                      continue;
                    }
                    else 
                break;
        } 
        if(n==array[m].length())
        {
            ArrayUtils.removeElement(array, array[s]);
        }
    }

如果元素与子字符串匹配,如何从列表中删除元素？

我尝试使用pop()和enumerate方法从列表中删除元素,但似乎我缺少一些需要删除的连续项:

sents = ['@$\tthis sentences needs to be removed', 'this doesnt',
     '@$\tthis sentences also needs to be removed',
     '@$\tthis sentences must be removed', 'this shouldnt',
     '# this needs to be removed', 'this isnt',
     '# this must', 'this musnt']

for i, j in enumerate(sents):
  if j[0:3] == "@$\t":
    sents.pop(i)
    continue
  if j[0] == "#":
    sents.pop(i)

for i in sents:
  print i

输出:

this doesnt
@$  this sentences must be removed
this shouldnt
this isnt
#this should …

是否有一个exsting字符串比较方法,它将根据两个字符串之间非匹配字符的第一次出现返回一个值？

即

string A = "1234567890"

string B = "1234567880"

我想得到一个值,这将使我看到匹配中断的第一次出现是A [8]

我知道文档中属性的部分值,但不是整个事物.有没有我可以用来表示任何价值的角色？例如,输入的标签值是"A.选择1".我知道它说"选择1",但不知道它是否会在"选择1"之前说"A"或"B".以下是相关的HTML.输入和标签还有其他属性,但每次呈现页面时它们都不相同,所以我不能将它们用作引用:

<tr>
<td><input type="checkbox" /><label>A. Choice 1</label></td>
</tr><tr>
    <td><input type="checkbox" /><label>B. Choice 2</label></td>
</tr><tr>
<td><input type="checkbox" /><label>C. Choice 3</label></td>
</tr><tr>
     <td><input type="checkbox" /><label>D. Choice 4</label></td>
</tr>

这是我用来选择标签旁边的输入的值为"选择1" 的XPath表达式,除了A在HTML前面的前面:

//td[label="Choice 1"]/input

我不知道HTML中的A是A还是A,等等.但是我确实知道正确的输入总是会有旁边的Choice 1文本.如果标签包含选项 1,如何选择它,而不是等于选择1？

根据关于Rabin-Karp字符串匹配算法的维基百科条目,它可以用于同时在字符串中查找几个不同的模式,同时仍然保持线性复杂性.很明显,当所有模式具有相同的长度时,这很容易完成,但是当我同时搜索具有不同长度的模式时,我仍然不知道如何保持O(n)复杂度.有人可以对此有所了解吗？

编辑(2011年12月):

维基百科文章已经更新,不再声称匹配O(n)中不同长度的多个模式.

给定一个字符串向量texts和一个模式向量patterns,我想找到每个文本的任何匹配模式.

对于小型数据集,可以在R中轻松完成grepl:

patterns = c("some","pattern","a","horse")
texts = c("this is a text with some pattern", "this is another text with a pattern")

# for each x in patterns
lapply( patterns, function(x){
  # match all texts against pattern x
  res = grepl( x, texts, fixed=TRUE )
  print(res)
  # do something with the matches
  # ...
})

此解决方案是正确的,但它不会扩展.即使使用适度更大的数据集(约500个文本和模式),这段代码也非常慢,在现代机器上每秒仅解决大约100个案例 - 考虑到这是一个粗略的字符串部分匹配,没有正则表达式(设置为fixed=TRUE),这是荒谬的.即使进行lapply并行也无法解决问题.有没有办法有效地重写这段代码？

谢谢,Mulone

我有一个特殊的问题,我想在许多字符串列表中搜索许多子字符串.以下是我要做的事情的要点:

listStrings = [ACDE, CDDE, BPLL, ... ]

listSubstrings = [ACD, BPI, KLJ, ...]

以上条目仅是示例.len(listStrings)是~60,000,len(listSubstrings)是~50,000-300,000,len(listStrings [i])是10到30,000.

我目前的Python尝试是:

for i in listSubstrings:
   for j in listStrings:
       if i in j:
          w.write(i+j)

或者沿着这些方向的东西.虽然这对我的任务起作用,但速度非常慢,使用一个核心并按照40分钟的顺序完成任务.有没有办法加快速度？

我不相信我可以用listStrings:listSubstrings制作一个dict,因为有可能需要在两端存储重复的条目(尽管我可以尝试这个,如果我能找到一种方法来附加一个唯一的标签每一个,因为dicts是如此快得多).同样,我认为我不能预先计算可能的子串.我甚至不知道搜索dict键是否比搜索列表更快(因为dict.get()它将提供特定输入而不是寻找子输入).在内存中搜索列表是否相对较慢？

问题:

我有一个promises数组,它被解析为一个字符串数组.现在,如果至少有一个字符串与正则表达式匹配,则测试应该通过.

目前,我使用简单的字符串连接解决它:

protractor.promise.all([text1, text2, text3]).then(function (values) {
    expect(values[0] + values[1] + values[2]).toMatch(/expression/);
});

显然,这不能很好地扩展,并且不是特别可读.

问题:

是可以使用它来解决定制茉莉匹配,或jasmine.any()或定制的非对称平等的测试？

我有一个21056字节的文件.

我在C中编写了一个程序,将整个文件读入缓冲区,然后使用多个搜索算法在文件中搜索82个字符的标记.

我已经使用了"精确字符串匹配算法"页面中所有算法的实现.我用过:KMP,BM,TBM和Horspool.然后我使用strstr并对每一个进行基准测试.

我想知道的是,每次strstr优于所有其他算法.有时候唯一更快的是BM.

不strstr应该是最慢的？

这是我的基准代码,其中包含基准测试BM的示例:

double get_time()
{
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart/(double)f.QuadPart;
}

before = get_time();
BM(token, strlen(token), buffer, len);
after = get_time();
printf("Time: %f\n\n", after - before);

有人可以向我解释为什么strstr表现优于其他搜索算法吗？如果需要,我会根据请求发布更多代码.

我想写一个正则表达式来搜索某些单词的存在,但它们的出现顺序无关紧要.

例如,搜索"Tim"和"stupid".我的正则表达式是Tim.*stupid|stupid.*Tim.但是有可能编写一个更简单的正则表达式(例如,这样两个单词在正则表达式中只出现一次)？