在O(N)时间复杂度中找到一个字符串在另一个字符串中出现的起始索引列表。

huangapple
go评论96阅读模式
英文:

Find the list of starting indexes of occurring of a string in another string in O(N) time complexity

问题

给定两个字符串：str1 和 str2。找到 str1 在 str2 中的所有起始索引。示例：
I/p = str1: abc, str2: abckdabcgfacabc
O/p = [0, 5, 12]

  1. public static List<Integer> firstMatchingIndexes(String str1, String str2) {
  2.     List<Integer> indexes = new ArrayList<>();
  3.     int end = 0, n = str2.length();
  4.     
  5.     for (; end < n; end++) {
  6.         int index = str2.substring(end, n).indexOf(str1) + end;
  7.         if (index != -1)
  8.             indexes.add(index);
  9.         else
  10.             break;
  11.         end = index + str1.length() - 1;
  12.     }
  13.     
  14.     return indexes;
  15. }

但这种方法使用了内部具有O(N)时间复杂度的indexOf()。KMP算法能在这里工作吗？

英文:

Given are two strings : str1 and str2. Find all the starting indexes of str1 in str2. Example:
I/p = str1: abc, str2: abckdabcgfacabc
O/p = [0, 5, 12]

  1. public static List&lt;Integer&gt; firstMatchingIndexes(String str1, String str2) {
  2. 	List&lt;Integer&gt; indexes = new ArrayList&lt;&gt;();
  3. 	int end = 0, n = str2.length();
  4. 	
  5. 	for(; end&lt;n; end++) {
  6. 		int index = str2.substring(end, n).indexOf(str1)+end;
  7. 		if(index!=-1)
  8. 			indexes.add(index);
  9. 		else
  10. 			break;
  11. 		end =index + str1.length()-1;
  12. 		
  13. 	}
  14. 	
  15. 	return indexes;
  16. }

But this approach uses indexOf() which internally has O(N) time complexity. Can KMP algorithm work here?

答案1

得分: 1

我能够使以下算法渲染出来。

纠正我如果我错了; 我相信这是O(n)复杂度的一个例子。
至于KMP算法，我不确定。

  1. List<Integer> firstMatchingIndexes(String stringA, String stringB) {
  2.     List<Integer> indices = new ArrayList<>();
  3.     boolean checking = false;
  4.     int indexA = 0, indexB = 0;
  5.     for (char character : stringB.toCharArray()) {
  6.         if (checking) {
  7.             if (character == stringA.charAt(indexA))
  8.                 if (indexA != stringA.length() - 1)
  9.                     indexA++;
  10.                 else {
  11.                     indices.add(indexB - (stringA.length() - 1));
  12.                     checking = false;
  13.                     indexA = 0;
  14.                 }
  15.             else {
  16.                 checking = false;
  17.                 indexA = 0;
  18.             }
  19.         } else if (character == stringA.charAt(indexA)) {
  20.             checking = true;
  21.             indexA++;
  22.         }
  23.         indexB++;
  24.     }
  25.     return indices;
  26. }

输出

  1. [0, 5, 12]
英文:

I was able to get the following algorithm to render.

Correct me if I'm wrong; I believe this is an example of O(n) complexity.
As for a KMP algorithm, I'm unsure.

  1. List&lt;Integer&gt; firstMatchingIndexes(String stringA, String stringB) {
  2.     List&lt;Integer&gt; indices = new ArrayList&lt;&gt;();
  3.     boolean checking = false;
  4.     int indexA = 0, indexB = 0;
  5.     for (char character : stringB.toCharArray()) {
  6.         if (checking) {
  7.             if (character == stringA.charAt(indexA))
  8.                 if (indexA != stringA.length() - 1)
  9.                     indexA++;
  10.                 else {
  11.                     indices.add(indexB - (stringA.length() - 1));
  12.                     checking = false;
  13.                     indexA = 0;
  14.                 }
  15.             else {
  16.                 checking = false;
  17.                 indexA = 0;
  18.             }
  19.         } else if (character == stringA.charAt(indexA)) {
  20.             checking = true;
  21.             indexA++;
  22.         }
  23.         indexB++;
  24.     }
  25.     return indices;
  26. }

Output

  1. [0, 5, 12]

答案2

得分: 1

是的，Knuth-Morris-Pratt算法在这里可以派上用场。

关于Knuth-Morris-Pratt算法的维基百科文章提供了该算法的伪代码。以下是将该伪代码转换为Java的版本：

  1.     static int[] kmpTable(String pattern) {
  2.         int n = pattern.length();
  3.         int[] partialMatchTable = new int[n+1];
  4.         int j = 0;
  6.         partialMatchTable[0] = -1;
  8.         for (int i = 1; i < n; i++, j++) {
  9.             if (pattern.charAt(i) == pattern.charAt(j)) {
  10.                 partialMatchTable[i] = partialMatchTable[j];
  11.             } else {
  12.                 partialMatchTable[i] = j;
  13.                 while (j >= 0 && pattern.charAt(i) != pattern.charAt(j)) {
  14.                     j = partialMatchTable[j];
  15.                 }
  16.             }
  17.         }
  18.         partialMatchTable[n] = j;
  19.         return partialMatchTable;
  20.     }
  21.  
  22.     static List<Integer> kmpSearch(String needle, String haystack) {
  23.         List<Integer> matches = new ArrayList<>();
  24.         int m = haystack.length();
  25.         int n = needle.length();
  26.         if (n > m) { // 为了避免O(m)运行时添加了这个条件
  27.             return matches; // 当needle太大时返回空列表
  28.         }
  29.         int[] partialMatchTable = kmpTable(needle);
  30.         int j = 0, k = 0;
  32.         while (j < m) {
  33.             if (needle.charAt(k) == haystack.charAt(j)) {
  34.                 j++;
  35.                 k++;
  36.                 if (k == n) {
  37.                     matches.add(j - k);
  38.                     k = partialMatchTable[k];
  39.                 }
  40.             } else {
  41.                 k = partialMatchTable[k];
  42.                 if (k < 0) {
  43.                     j++;
  44.                     k++;
  45.                 }
  46.             }
  47.         }
  48.         return matches;
  49.     }
  51.     public static void main(String args[])
  52.     {
  53.         System.out.println("matches: " + kmpSearch("abc", "abckdabcgfacabc"));
  54.     }

这将输出：

  1. matches: [0, 5, 12]

维基百科对于时间复杂度的说明如下：

Knuth-Morris-Pratt算法的复杂度为O(𝑛+𝑚)，其中𝑛是模式的长度。

当考虑到构建长度为𝑚的模式的部分匹配表所需的时间时：

由于算法的两部分分别具有O(𝑚)和O(𝑛)的复杂度，整体算法的复杂度为O(𝑚+𝑛)。

然而，当𝑛 ≤ 𝑚 时，我们可以说它是O(𝑚)。当使用比要搜索的字符串更长的模式进行搜索时，该算法可以跳过构建此搜索字符串的部分匹配表，并以空列表退出（参见维基百科伪代码中不存在的已注释代码）。因此，它总是O(𝑛)。

英文:

Yes, the Knuth–Morris–Pratt algorithm can be of use here.

The Wikipedia article on the Knuth–Morris–Pratt algorithm provides pseudocode for the algorithm. Here is that pseudocode ported to Java:

  1.     static int[] kmpTable(String pattern) {
  2. int n = pattern.length();
  3. int[] partialMatchTable = new int[n+1];
  4. int j = 0;
  5. partialMatchTable[0] = -1;
  6. for (int i = 1; i &lt; n; i++, j++) {
  7. if (pattern.charAt(i) == pattern.charAt(j)) {
  8. partialMatchTable[i] = partialMatchTable[j];
  9. } else {
  10. partialMatchTable[i] = j;
  11. while (j &gt;= 0 &amp;&amp; pattern.charAt(i) != pattern.charAt(j)) {
  12. j = partialMatchTable[j];
  13. }
  14. }
  15. }
  16. partialMatchTable[n] = j;
  17. return partialMatchTable;
  18. }
  19. static List&lt;Integer&gt; kmpSearch(String needle, String haystack) {
  20. List&lt;Integer&gt; matches = new ArrayList&lt;&gt;();
  21. int m = haystack.length();
  22. int n = needle.length();
  23. if (n &gt; m) { // Added this to avoid O(m) runtime
  24. return matches; // Return empty list when needle is too large
  25. }
  26. int[] partialMatchTable = kmpTable(needle);
  27. int j = 0, k = 0;
  28. while (j &lt; m) {
  29. if (needle.charAt(k) == haystack.charAt(j)) {
  30. j++;
  31. k++;
  32. if (k == n) {
  33. matches.add(j - k);
  34. k = partialMatchTable[k];
  35. }
  36. } else {
  37. k = partialMatchTable[k];
  38. if (k &lt; 0) {
  39. j++;
  40. k++;
  41. }
  42. }
  43. }
  44. return matches;
  45. }
  46. public static void main(String args[])
  47. {
  48. System.out.println(&quot;matches: &quot; + kmpSearch(&quot;abc&quot;, &quot;abckdabcgfacabc&quot;));
  49. }

This outputs:

  1. matches: [0, 5, 12]

Wikipedia says about the time complexity:

> the Knuth–Morris–Pratt algorithm has complexity O(𝑛), where 𝑛 is the length of 𝑆.

And when taking into account the time needed for building the partial-match table for a pattern of length 𝑘:

> Since the two portions of the algorithm have, respectively, complexities of O(𝑘) and O(𝑛), the complexity of the overall algorithm is O(𝑛 + 𝑘).

We can however say it is O(𝑛) when 𝑘 ≤ 𝑛. When searching with a pattern that is longer than the string to search in, the algorithm could just skip building the partial match table for such a search string and exit with an empty list (See commented code that is not present in Wikipedia's pseudocode). That way it is always O(𝑛).

huangapple
  • 本文由 发表于 2023年5月22日 08:36:10
  • 转载请务必保留本文链接：https://go.coder-hub.com/76302458.html
  • algorithm
  • data-structures
  • java
  • knuth-morris-pratt
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定