2

大家好，我遇到了家庭作业问题，它要求我找到字符串的所有不同子字符串。我已经实现了一种方法，它会告诉你字符串的所有子字符串，但我需要帮助弄清楚如何不计算一个已经被计算为子字符串的子字符串，因为分配是要找到不同的子字符串。

public int printSubstrings1(int length)
{ 
    for(int i=0; i<text.length()-length+1;i++)
    {
        String sub = text.substring(i,length+i);

        counter++;
    }
    return counter;

}

在这里，我从给定的字符串中传递我想要的子字符串的长度。我正在通过另一种方法做到这一点。

所以给出的示例字符串是“fred”，而不是不同的子字符串将是 10。我的方法将输出正确答案，因为字符串不包含任何重复的字母。我被困在我确实得到重复子字符串的部分。

如果我输入弗雷德。这是我的方法将输出的

长度 1
f
r
e
d
长度 2
fr
ed 长度 3
fre 红色 长度 4 fred




4

6 回答 6

4 
public ArrayList<String> getAllUniqueSubset(String str) {
        ArrayList<String> set = new ArrayList<String>();
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j < str.length() - i; j++) {
                String elem = str.substring(j, j + (i+1));
                if (!set.contains(elem)) {
                    set.add(elem);
                }
            }
        }
        return set;
    }
于 2014-06-23T17:51:40.903 回答
3

Here the example with a Set

public int printSubstrings1(int length) {
    Set<String> set = new HashSet<String>();
    for(int i=0; i < text.length() - length + 1; i++) {
        String sub = text.substring(i,length+i);
        set.add(sub);
    }
    for (String str : set) {
        System.out.println(str);
    }
    return set.size();
}
于 2012-11-03T21:46:42.530 回答
0

Insert any new sub string into an array and check if it is already available available there don't add it to the array else do. When done loop through the array and print out the distinct sub strings.

To check if an element exists in an array create a function that takes an array and a value as parameters. It would loop through the array looking for the value if found return true. Out of the loop return false.

e.g. 

public static boolean(String target, String[] arr)
{
  for(int i = 0; i < arr.length; i++){
      if(arr[i].equals(target))
         return true;
  }
   return false;
}
于 2012-11-03T21:46:33.710 回答
0

我点击了这个链接。承认来自quora中类似答案的内容

该解决方案包括构建后缀数组，然后根据最长公共前缀查找不同子字符串的数量。

这里的一个关键观察是：

如果您查看字符串的每个后缀的前缀，您已经涵盖了该字符串的所有子字符串。

举个例子：香蕉

后缀为： 0) BANANA 1) ANANA 2) NANA 3) ANA 4) NA 5) A

如果我们对上述后缀集进行排序，则通过前缀会容易得多，因为我们可以轻松跳过重复的前缀。

排序后缀集：5) A 3) ANA 1) ANANA 0) BANANA 4) NA 2) NANA

从现在开始，

LCP = 2 个字符串的最长公共前缀。

初始化

ans = 长度（第一个后缀）= 长度（“A”）= 1。

现在考虑来自上述排序后缀集合的连续后缀对，即[A, ANA]、[ANA, ANANA]、[ANANA, BANANA]等。

我们可以看到，LCP("A", "ANA") = "A"。

不属于公共前缀的所有字符都构成不同的子字符串。在上述情况下，它们是“N”和“A”。所以应该将它们添加到ans中。

所以我们有 1 2 ans += length("ANA") - LCP("A", "ANA") ans = ans + 3 - 1 = ans + 2 = 3

对下一对连续的后缀执行相同的操作：["ANA", "ANANA"]

1 2 3 4 LCP("ANA", "ANANA") = "ANA"。ans += length("ANANA") - length(LCP) => ans = ans + 5 - 3 => ans = 3 + 2 = 5。

同样，我们有：

1 2 LCP("ANANA", "BANANA") = 0 ans = ans + length("BANANA") - 0 = 11

1 2 LCP("香蕉", "NA") = 0 ans = ans + 长度("NA") - 0 = 13

1 2 LCP("NA", "NANA") = 2 ans = ans + length("NANA") - 2 = 15

因此，字符串“BANANA”的不同子字符串的数量 = 15。

于 2017-08-10T17:12:12.673 回答
0

有两种方法可以做到这一点，不确定你的老师是否允许，但我将使用 HashSet 来实现唯一性。

不使用'substring()'：

void uniqueSubStrings(String test) {
HashSet < String > substrings = new LinkedHashSet();
char[] a = test.toCharArray();
for (int i = 0; i < test.length(); i++) {
    substrings.add(a[i] + "");
    for (int j = i + 1; j < test.length(); j++) {
        StringBuilder sb = new StringBuilder();
        for (int k = i; k <= j; k++) {
            sb.append(a[k]);
        }
        substrings.add(sb.toString());
    }
}
System.out.println(substrings);

}

使用“子字符串”：

    void uniqueSubStringsWithBuiltIn(String test) {
    HashSet<String> substrings = new LinkedHashSet();

    for(int i=0; i<test.length();i++) {
        for(int j=i+1;j<test.length()+1;j++) {
            substrings.add(test.substring(i, j));
        }
    }
        System.out.println(substrings);}
于 2019-10-01T19:10:46.847 回答
0

该算法仅使用 Z 函数 / Z 算法。

对于单词的每个前缀 i，将其反转并对其执行 z_function 。以 结尾的新的不同子字符串的i数量(the length of the prefix) — (maximum value in the z_function array)。伪代码如下所示：

string s; cin >> s;
int sol = 0
foreach i to s.size()-1
    string x = s.substr( 0 , i+1 );
    reverse( x.begin() , x.end() );
    vector<int> z = z_function( x );
    //this works too
    //vector<int> z = prefix_functionx(x); 
    int mx = 0;
    foreach j to x.size()-1
        mx = max( mx , z[j] );
    sol += (i+1) - mx; 

cout << sol;

该算法的时间复杂度为 O(n^2)。最大值也可以从 z_function 返回。

资源。

这不是我原来的答案。我只是链接到它并粘贴它以防链接断开。

于 2017-01-17T02:04:20.830 回答