首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >重复但重叠字符串的算法

重复但重叠字符串的算法
EN

Stack Overflow用户
提问于 2012-07-15 15:34:57
回答 6查看 1.1K关注 0票数 17

我需要编写一个方法,其中给我一个字符串s,并且我需要两次返回包含s的最短字符串作为一个连续的子字符串。

但是,两次出现的s可能会重叠。例如,

  • aba返回ababa
  • xxxxx返回xxxxxx
  • abracadabra返回abracadabracadabra

到目前为止,我的代码是:

import java.util.Scanner;

public class TwiceString {

    public static String getShortest(String s) {
        int index = -1, i, j = s.length() - 1;
        char[] arr = s.toCharArray();
        String res = s;

        for (i = 0; i < j; i++, j--) {
            if (arr[i] == arr[j]) {
                index = i;
            } else {
                break;
            }
        }

        if (index != -1) {
            for (i = index + 1; i <= j; i++) {
                String tmp = new String(arr, i, i);
                res = res + tmp;
            }
        } else {
            res = res + res;
        }

        return res;
    }

    public static void main(String args[]) {
        Scanner inp = new Scanner(System.in);
        System.out.println("Enter the string: ");
        String word = inp.next();

        System.out.println("The requires shortest string is " + getShortest(word));
    }
}

我知道我可能在算法层面上错了,而不是在编码层面上。我的算法应该是什么?

EN

回答 6

Stack Overflow用户

发布于 2012-07-15 16:42:09

使用suffix tree。特别是,在为s构建了树之后,转到表示整个字符串的叶子并向上移动,直到看到另一个字符串结束标记。这将是最长后缀的叶,也是s的前缀。

票数 9
EN

Stack Overflow用户

发布于 2012-07-15 20:07:13

正如@phs已经说过的,部分问题可以转化为“找到s的最长前缀,也是s的后缀”,没有树的解决方案可能是这样的:

public static String getShortest(String s) {
    int i = s.length();
    while(i > 0 && !s.endsWith(s.substring(0, --i))) 
        ;
    return s + s.substring(i);
}
票数 3
EN

Stack Overflow用户

发布于 2012-07-15 15:48:39

找到索引后,即使它是-1,也只需要将从index + 1 (因为索引是最后一个匹配的字符索引)到字符串末尾的子字符串追加到原始字符串。String中有一个方法可以获取这个子字符串。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/11490290

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档