标签: substring

我知道这里已经有几个类似的问题,但我需要一些针对我的案例的建议(找不到类似的东西).

我必须搜索非常大量的数据,以获得大约十亿倍的子字符串(10亿字节中的10个字节).干草堆没有变化,所以如果需要我可以承受大量的预计算.我只需要搜索部分尽可能快.

我发现算法需要O(n)时间(n =干草堆大小,m =针大小),而幼稚搜索需要O(n + m).由于这个特殊情况下的m非常小,我还能研究其他算法吗？

编辑:谢谢大家的建议!更多信息 - 数据可以被认为是随机位,所以我认为任何类型的索引/排序都不可能.要搜索的数据可以是任何内容,而不是英语单词或任何可预测的内容.

获取字符串的子字符串是一种非常常见的字符串操作操作,但我听说Java和.NET平台之间的性能/实现可能存在很大差异.具体来说,我听说在Java中,java.lang.String提供恒定时间操作substring,但在.NET中,System.String提供线性性能Substring.

这些真的是这样吗？可以在文档/源代码等中确认吗？此实现是特定的,还是由语言和/或平台指定的？每种方法的优缺点是什么？一个人从一个平台迁移到另一个平台应该寻找什么来避免陷入任何性能陷阱？

我有一个字母组合字母和数字.对于我的应用程序,我必须用字母和数字分隔一个字符串:例如:如果我的字符串是"12jan"我将分别得到"12""jan"..

class StringTesting {
    public static void main(String args[])
    {
        String str = "abcd";
        String str1 = new String("abcd");
        String str2 = str.substring(0,2);
        String str3 = str.substring(0,2);
        String str4 = str.substring(0,str.length());
        String str5 = str1.substring(0,2);
        String str6 = str1.substring(0,2);
        String str7 = str1.substring(0,str1.length());

        System.out.println(str2 == str3);
        System.out.println(str == str4);
        System.out.println(str5 == str6);
        System.out.println(str1 == str7);
    }
}

这是我在java 1.6.0_27上得到的输出:

false
true
false
true

有人可以解释输出.我知道Java区分存储在堆中的String和存储在String"common pool"中的String(可以是interned).在内部,他们的表现如何不同.它是如何改变子串算法的.请在适当的地方引用书籍/文章/博客等.

我正在寻找很多短文本(haystack)中很短的子串(模式,针).但是,我不太确定在天真的暴力方法之外使用哪种方法.

背景:我正在做一个有趣的侧面项目,我收到多个用户的短信聊天记录(2000-15000行文本和2-50个用户),我想在聊天中找到所有各种模式匹配根据我提出的预定单词记录日志.到目前为止,我有大约1600种模式,我正在寻找,但我可能会寻找更多.

因此,例如,我想找到在平均文本消息日志中使用的与食物相关的单词的数量,例如"汉堡包","披萨","可乐","午餐","晚餐","餐馆","麦当劳".虽然我给出了英语示例,但实际上我将使用韩语作为我的程序.这些指定单词中的每一个都有各自的分数,我将其分别作为键和值放在哈希映射中.然后,我展示了食物相关单词的最佳得分者以及这些用户用于食物单词的最常用单词.

我目前的方法是通过空格消除每行文本,并通过使用haystack包含模式的contains方法(使用indexOf方法和朴素子串搜索算法)处理大海捞针中的每个单词.

wordFromInput.contains(wordFromPattern);

举一个例子,聊天中有17个用户,13000行文本和1600个模式,我发现这个方法整个程序用了12-13秒.在我正在开发的Android应用程序上,处理需要2分30秒,这太慢了.

最初,我尝试使用哈希映射并仅仅获取模式而不是在ArrayList中搜索它,但我意识到这是......

哈希表不可能

我试图用子串做什么.

我查看了Stackoverflow,发现了很多有用的相关问题,比如这两个:

1和2.我对各种字符串算法(Boyer Moore,KMP等)比较熟悉

我最初认为天真的方法当然是我案例中最糟糕的算法类型,但是在发现这个问题后,我意识到我的情况(简短模式,短文本),实际上可能对天真更有效方法.但我想知道是否有一些我完全忽视的东西.

以下是我的代码片段,但是如果有人想要更具体地看到我的问题.

虽然我删除了大部分代码以简化它,但我使用实际匹配子字符串的主要方法是matchWords()方法.

我知道这是非常丑陋和糟糕的代码(5代表循环...),所以如果有任何建议,我也很高兴听到它.

所以要清理它:

• 来自聊天记录的文本行(2000-10,000 +),haystack
• 1600多种图案,针
• 虽然包括一些英语,但主要使用韩语字符
• 蛮力天真的方法简直太慢,但争论是否有其他替代方案,即使有,但鉴于短模式和文本的性质,它们是否实用.

我只想在思考过程中得到一些意见,可能还有一些一般的建议.但另外,如果可行,我想对特定算法或方法提出一些具体建议.

是否有一个函数检查字符串是否以某个子字符串结尾？Python有endswith:

>>> "victory".endswith("tory")
True

我们有一个字符串.

ABAEABABEABE

现在我们必须检查是否存在一个子字符串,接下来是另一个子字符串,它与第一个子字符串完全相同.

在这个例子中:ABAEAB ABE ABE
ABE之后是ABE,它是两个相同的子串.

在这个例子中:

AAB

它只是A,因为A后跟另一个A.

在这个例子中:
ABCDEFGHIJKLMNO
没有这样的子串,所以答案是NO.

我只设法找到一个运行在O(n ^ 2)的算法.这是哈希及其前缀.然后,对于每个字母,我们简单地展开并检查以该字母结尾的所有单词.有n个字母.我们需要扩展它n次.所以它是O(n ^ 2).我相信应该有一个针对这个问题的O(n log n)算法.

有没有人有更好的主意？

我有一个字符串,说:

Product Description [White]

我想White使用PostgreSQL子串函数从该字符串中提取括号内的任何内容(在本例中).我可以使用它来工作regexp_matches,但是返回一个我不想要的数组,除非我别无选择.

我试过了:

• substring('string' from '[(.)]') >>> NULL
• substring('string' from '\[(.)\]') >>> NULL
• substring('string' from '\\[(.)\\]') >>> NULL

但这有效:

• substring('string' from 'W(.)i]') >>> h

我究竟做错了什么？

我有以下的代码,遍历对Java DateTimeFormatter的图形组合"E".."EEEE"和"M".."MMMM".

我的问题是,在这种情况下,是否存在使用Java Streams的惯用方法(或者只是'更惯用')？

import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class DateTimeFormattingStackOverflow {
    static LocalDateTime dateTime = LocalDateTime.now();

    static Stream<String> substrings(String str) {
        return IntStream.range(1, str.length() + 1)
                .mapToObj(i -> str.substring(0, i));
    }

    static void printDateTime(String pattern) {
        DateTimeFormatter dtf = DateTimeFormatter.ofPattern(pattern);
        System.out.println(pattern + ", " + dtf.format(dateTime));
    }

    public static void main(String[] args) {
        Stream<String> patterns = substrings("EEEE")
                .flatMap(e -> substrings("MMMM").map(m -> e + " " + m))
                .map(em -> em …

所以我有这个快速的代码:

func didReceiveResponse(response:String) {
  ...
  let substr = response[11...]

根据我的解释,substr应该是一个子串,引用响应字符串中索引11之后的所有字符.

实际发生的是这个编译器错误:

Cannot subscript a value of type 'String' with an index of type 'CountablePartialRangeFrom<Int>'

这似乎应该是显而易见的,有人可以帮忙吗？