字符串例题

京东笔试题

给定一个字符串s,请计算输出含有连续两个s作为子串的最短字符串。注意两个s可能有重叠部分。例如，"ababa"含有两个“aba".

输入描述

输入包括一个字符串s,字符串长度length(1<=length<=50),s中每个字符都是小写字符。

输出描述

输出一个字符串，即含有连续两个s作为子串的最短字符串。

示例1

输入：abracadabra

输出：abracadabracadabra

题解

求出原字符串的next数组，假设原字符串长度为n，再求next[n]位置的值，表示后面需要补下标为next[n]开始到结尾的字符，举个例子：str=abracadabra，next值分别是-1,0,0,0,1,0,1,0,1,2,2，然后再求next[n]的值为4，所以从下标为4开始一直往后的字符全部添加到结尾就变成了abracadabracadabra

代码

import java.util.*;
public class Main {
    public static String res(String str1) {
        String tmp = "";
        char[] s1 = str1.toCharArray();
        int[] next = next(s1);
        for(int i = next[str1.length()];i < str1.length();i++)
            tmp += str1.charAt(i);
        return str1 + tmp;
    }
    public static int[] next(char[] s1) {
        if(s1.length == 0)
            return new int[] {-1};
        int[] next = new int[s1.length + 1];
        next[0] = -1;
        next[1] = 0;
        int cn = 0;
        int i = 2;
        while(i <= s1.length) {
            if(s1[i - 1] == s1[cn])
                next[i++] = ++cn;
            else if(cn > 0)
                cn = next[cn];
            else
                next[i++] = 0;
        }
        return next;
    }
}

某歌面试题

在末尾添加最少字符使得原字符串成为回文串

题解

manacher算法变形，当回文右边界R==str.length时，对应的[0,L)翻转过来添加到字符串后面即可

代码

public static char[] manacherString(String str) {
    char[] charArr = str.toCharArray();
    char[] res = new char[str.length() * 2 + 1];
    int index = 0;
    for(int i = 0;i < res.length;i++)
        res[i] = (i & 1) == 0 ? '#' : charArr[index++];
    return res;
}
public static String maxLcpsLength(String str) {
    if(str == null || str.length() == 0) 
        return "";
    char[] charArr = manacherString(str);
    int[] pArr = new int[charArr.length];//回文半径数组
    int index = -1,pR = -1;//回文中心和回文最右边界
    int maxContainsEnd = -1;
    for(int i = 0;i != charArr.length;i++) {
        pArr[i] = pR > i ? Math.min(pArr[2 * index - i],pR - i) : 1;
        while(i + pArr[i] < charArr.length && i - pArr[i] > -1) {
            if(charArr[i + pArr[i]] == charArr[i - pArr[i]])
                pArr[i]++;
            else 
                break;
        }
        if(i + pArr[i] > pR) {
            pR = i + pArr[i];
            index = i;
        }
        if(pR == charArr.length) {
            maxContainsEnd = pArr[i];
            break;
        }                
    }
    char[] res = new char[str.length() - maxContainsEnd + 1];
    for(int i = 0;i < res.length;i++) 
        res[res.length - 1 - i] = charArr[i * 2 + 1];
    return String.valueOf(res);
}