2

有人可以向我解释如何迭代地解决子字符串问题吗？

问题：给定两个字符串S = S 1 S 2 S 3 ...<em>S n和T = T 1 T 2 T 3 ...<em>T m，其中m小于或等于n，确定T是否为S的子串。

4

11 回答 11

4

这是字符串搜索算法的列表

根据您的需要，不同的算法可能更适合，但Boyer-Moore是一种流行的选择。

于 2009-09-02T20:06:46.447 回答
3

不确定您使用的是哪种语言，但这里有一个 C# 示例。这是一个大约 n 2的算法，但它可以完成工作。

bool IsSubstring (string s, string t)
{
   for (int i = 0; i <= (s.Length - t.Length); i++)
   {
      bool found = true;

      for (int j = 0; found && j < t.Length; j++)
      {
         if (s[i + j] != t[j])
             found = false;
      }

      if (found)
         return true;
   }

   return false;
}
于 2009-09-02T20:13:43.313 回答
3

如果S i+1 S i +2 ...<em>S i + m = T 1 T 2 ...<em>T m，一个简单的算法将在 S 的每个位置 0 < i ≤ n - m处进行测试。对于n =7 和m =5：

i=0:   S 1 S 2 S 3 S 4 S 5 S 6 S 7
      | | | | |
      T 1 T 2 T 3 T 4 T 5

i=1：   S 1 S 2 S 3 S 4 S 5 S 6 S 7
        | | | | |
        T 1 T 2 T 3 T 4 T 5

i=2：   S 1 S 2 S 3 S 4 S 5 S 6 S 7
          | | | | |
          T 1 T 2 T 3 T 4 T 5

伪代码中的算法：

// we just need to test if n ≤ m 
IF n > m:
    // for each offset on that T can start to be substring of S
    FOR i FROM 0 TO n-m:
        // compare every character of T with the corresponding character in S plus the offset
        FOR j FROM 1 TO m:
            // if characters are equal
            IF S[i+j] == T[j]:
                // if we’re at the end of T, T is a substring of S
                IF j == m:
                    RETURN true;
                ENDIF;
            ELSE:
                BREAK;
            ENDIF;
        ENDFOR;
    ENDFOR;
ENDIF;
RETURN false;
于 2009-09-02T20:14:34.793 回答
2 
if (T == string.Empty) return true;
for (int i = 0; i <= S.Length - T.Length; i++) {
    for (int j = 0; j < T.Length; j++) {
        if (S[i + j] == T[j]) {
            if (j == (T.Length - 1)) return true;
        }
        else break;
    }
}
return false;
于 2009-09-02T20:09:54.413 回答
1

这可能与上面的子字符串算法列表是多余的，但我总是被 KMP 逗乐（http://en.wikipedia.org/wiki/Knuth –Morris–Pratt_algorithm）

于 2009-09-03T07:16:57.070 回答
1

它会是这样的：

m==0? return true
cs=0
ct=0
loop
    cs>n-m? break
    char at cs+ct in S==char at ct in T?
    yes:
        ct=ct+1
        ct==m? return true
    no:
        ct=0
        cs=cs+1

end loop
return false
于 2009-09-02T20:09:03.417 回答
1 
// runs in best case O(n) where no match, worst case O(n2) where strings match

var s = "hippopotumus"
var t = "tum"

for(var i=0;i<s.length;i++)
    if(s[i]==t[0])
        for(var ii=i,iii=0; iii<t.length && i<s.length; ii++, iii++){
            if(s[ii]!=t[iii]) break
            else if (iii==t.length-1) console.log("yay found it at index: "+i)
        }
于 2012-09-24T20:36:40.073 回答
0

是一种O(n*m)算法，其中n和m是每个字符串的大小。在 C# 中，它类似于：

   public static bool IsSubtring(char[] strBigger, char[] strSmall)
        {
            int startBigger = 0;
            while (startBigger <= strBigger.Length - strSmall.Length)
            {
                int i = startBigger, j = 0;

                while (j < strSmall.Length && strSmall[j] == strBigger[i])
                {
                    i++;
                    j++;
                }

                if (j == strSmall.Length)
                    return true;
                startBigger++;
            }

            return false;
        }
于 2013-10-08T16:49:46.467 回答
0

我知道我迟到了，但这是我的版本（在 C# 中）：

    bool isSubString(string subString, string supraString)
    {
        for (int x = 0; x <= supraString.Length; x++)
        {
            int counter = 0;
            if (subString[0] == supraString[x]) //find initial match
            {
                for (int y = 0; y <= subString.Length; y++)
                {
                    if (subString[y] == supraString[y+x])
                    {
                        counter++;
                        if (counter == subString.Length)
                        {
                            return true;
                        }
                    } 
                }
            }
        }
        return false;
    }
于 2014-03-12T16:44:34.580 回答
0

这是我的 PHP 变体，其中包括检查以确保在搜索期间 Needle 不超过 Haystacks 长度。

<?php

function substring($haystack,$needle) {
        if("" == $needle) { return true; }
        echo "Haystack:\n$haystack\n";
    echo "Needle:\n$needle\n";

        for($i=0,$len=strlen($haystack);$i<$len;$i++){
                if($needle[0] == $haystack[$i]) {
                        $found = true;
                        for($j=0,$slen=strlen($needle);$j<$slen;$j++) {
                                if($j >= $len) { return false; }
                                if($needle[$j] != $haystack[$i+$j]) {
                                        $found = false;
                                        continue;
                                }
                        }
                        if($found) {
                                echo " . . . . . . SUCCESS!!!! startPos: $i\n";
                                return true;
                        }
                }
        }
        echo " . . . . . . FAILURE!\n" ;
        return false;
}

assert(substring("haystack","hay"));
assert(!substring("ack","hoy"));
assert(substring("hayhayhay","hayhay"));
assert(substring("mucho22","22"));
assert(!substring("str","string"));
?>

留下一些回声。如果他们冒犯了你，请删除！

于 2012-04-25T00:38:53.323 回答
0

虽然它的帖子很老，但我正在尝试回答它。如有不妥请指正

package com.amaze.substring;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class CheckSubstring {

/**
 * @param args
 * @throws IOException 
 */
public static void main(String[] args) throws IOException {
    // TODO Auto-generated method stub

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    System.out.println("Please enter the main string");
    String mainStr = br.readLine();

    System.out.println("Enter the substring that has to be searched");
    String subStr = br.readLine();

    char[] mainArr = new char[mainStr.length()];
    mainArr = mainStr.toCharArray();
    char[] subArr = new char[subStr.length()];
    subArr = subStr.toCharArray();
    boolean tracing = false;
    //System.out.println("Length of substring is "+subArr.length);
    int j = 0;

    for(int i=0; i<mainStr.length();i++){

        if(!tracing){
            if(mainArr[i] == subArr[j]){
                tracing = true;
                j++;
            }
        } else {
            if (mainArr[i] == subArr[j]){
                //System.out.println(mainArr[i]);
                //System.out.println(subArr[j]);
                j++;
                System.out.println("Value of j is "+j);
                if((j == subArr.length)){
                    System.out.println("SubString found");
                    return;
                }
            } else {
                j=0;
                tracing = false;
            }
        }
    }

    System.out.println("Substring not found");

}

}
于 2013-11-17T17:05:55.343 回答