1. 最长公共子串
1.1 只返回子串最大长度
问题：给定两个字符串，返回两个字符串中最长子串的长度。
/**
* 返回两个数组中公共的、长度最长的子数组的长度
* @param A
* @param B
* @return
*/
public int findLength(int[] A, int[] B) {
// dp[i][j]表示下标0~i-1,0~j-1的最大长度2
int[][] dp=new int[A.length+1][B.length+1];
dp[0][0]=0;
int ans=0;
for (int i = 1; i <=A.length; i++) {
for (int j = 1; j <=B.length; j++) {
if (A[i-1]==B[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
ans=Math.max(ans,dp[i][j]);
}
}
return ans;
}
1.2 返回最大长度的子串
问题：给定两个字符串，返回两个字符串中最长子串。
/**
* 返回最长公共子串
* @param s1
* @param s2
* @return
*/
public String findCommons(String s1, String s2) {
if (s1.length()>s2.length()){
String temp=s1;
s1=s2;
s2=temp;
}
// dp[i][j]表示下标0~i-1,0~j-1的最大长度
int[][] dp=new int[s1.length()+1][s2.length()+1];
// 最大长度
int maxLength=0;
// 最大长度最后一个字符下标
int lastIndex=0;
dp[0][0]=0;
for (int i = 1; i <=s1.length(); i++) {
for (int j = 1; j <=s2.length(); j++) {
if (s1.charAt(i-1)==s2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
if (dp[i][j]>maxLength){
maxLength=dp[i][j];
lastIndex=i-1;
}
}
}
}
return s1.substring(lastIndex-maxLength+1,maxLength);
}
2. 最长公共子序列
2.1 只返回最长公共子序列长度
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
// dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列长度为dp[i][j]
int[][] dp = new int[len1+1][len2+1];
for (int i=1; i<=len1; ++i) {
for (int j=1; j<=len2; ++j) {
if (text1.charAt(i-1) == text2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[len1][len2];
}
2.2 返回最长公共子序列
public void longestCommonSubsequence(String s1, String s2) {
int len1=s1.length();
int len2=s2.length();
// dp数组，保存最大长度
int[][] dp=new int[len1+1][len2+1];
// 标志数组，记录当前状态是从哪个状态转变过来的（三种）
int[][] flag=new int[len1+1][len2+1];
// 1.填充dp和flag
for (int i = 1; i <=len1; i++) {
for (int j = 1; j <=len2; j++) {
// 1.第一种状态
if (s1.charAt(i-1)==s2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
flag[i][j]=1;
// 2.第二种状态
}else if (dp[i-1][j]>=dp[i][j-1]){
dp[i][j]=dp[i-1][j];
flag[i][j]=0;
// 3.第三种状态
}else {
dp[i][j]=dp[i][j-1];
flag[i][j]=-1;
}
}
}
if (len1<len2){
String t=s1;
s1=s2;
s2=t;
}
// 2.回溯较长字符串找结果
display(s1,flag,len1,len2);
}
/**
* 递归查找结果
* @param s1
* @param flag
* @param i
* @param j
*/
private static void display(String s1, int[][] flag, int i, int j) {
if(i == 0 || j == 0) {
return;
}
if(flag[i][j] == 1)
{
display(s1, flag, i-1, j-1);
System.out.print(s1.charAt(i-1) + " ");
}
else if(flag[i][j] == 0)
{
display(s1, flag, i-1, j);
}
else if(flag[i][j] == -1)
{
display(s1, flag, i, j-1);
}
}
3.最长递增子序列
3.1 只返回最大长度
public int lengthOfLIS(int[] nums) {
if (nums==null||nums.length==0){
return 0;
}
int[] dp=new int[nums.length];
dp[0]=1;
int maxdp=1;
int n=nums.length;
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxdp = Math.max(maxdp, dp[i]);
}
return maxdp;
}
3.2 返回序列
public int[] LIS (int[] arr) {
// dp[i]表示以arr[i]结尾的最长上升子序列长度
int[] dp=new int[arr.length];
// 最大长度
int maxLen=0;
// 最大长度的最后一个元素下标
int index=0;
// 1.求每个位置的最大长度
for (int i = 0; i < arr.length; i++) {
dp[i]=1;
for (int j = 0; j <i ; j++) {
if (arr[i]>arr[j]){
dp[i]=Math.max(dp[i],dp[j]+1);
}
if (dp[i]>maxLen){
maxLen=dp[i];
index=i;
}
}
}
// 2.求结果数组
int[] res=new int[maxLen];
res[--maxLen]=arr[index];
for (int i = index; i>=0; i--) {
if ((arr[i]<arr[index])&&(dp[i]==dp[index]-1)){
res[--maxLen]=arr[i];
index=i;
}
}
return res;
}
4.最长回文子串
问题：给你一个字符串 s，找到 s 中最长的回文子串。
public String longestPalindrome(String s) {
int n = s.length();
// dp[i][j]表示下标i~j之间的字符串是不是回文串
boolean[][] dp = new boolean[n][n];
String ans = "";
// 遍历所有长度
for(int len = 0; len < s.length() ; len ++){
//从start开始的len长度
for (int start = 0; start < dp.length - len; start++) {
int end = start + len;
if(len == 0) {
dp[start][end] = true;
} else if(len == 1) {
dp[start][end] = s.charAt(start) == s.charAt(end);
} else {
dp[start][end] = s.charAt(start) == s.charAt(end) && dp[start + 1][end - 1];
}
if(dp[start][end] && len >= ans.length()){
ans = s.substring(start, end + 1);
}
}
}
return ans;
}
5.最长回文子序列
private int findLongestPalindromeSubSeq(String s) {
if(s==null||s.length()==0){
return 0;
}
int len=s.length();
// dp[i][j]表示区间i~j的最长回文子序列长度
int[][] dp=new int[len][len];
for (int i = 0; i < len; i++) {
dp[i][i]=1;
}
for (int i = len-1; i >=0; i--) {
for (int j = i+1; j < len; j++) {
if (s.charAt(i)==s.charAt(j)){
dp[i][j]=dp[i+1][j-1]+2;
}else {
dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
}
}
}
return dp[0][len-1];
}
6.最长无重复子串
问题：给定一个数组arr，返回arr的最长的无重复子串的长度(无重复指的是所有数字都不相同)。
public int maxLength (int[] arr) {
// write code here
int maxLength=0;
int start=0,end=0;
HashMap<Integer,Integer> map=new HashMap<>();
for (; end<arr.length; end++) {
if (map.containsKey(arr[end])){
//注意：这里一定要取最大的start，不然就错误了
//为什么？ 因为重复数字的索引很可能比start小
start=Math.max(start,map.get(arr[end])+1);
}
maxLength=Math.max(maxLength,end-start+1);
map.put(arr[end],end);
}
return maxLength;
}
7.最长重复子串
问题：一个重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串给定一个字符串，请编写一个函数，返回其最长的重复字符子串。若不存在任何重复字符子串，则返回0。
public int solve (String a) {
int n=a.length();
int len=n/2;
for (int i = len; i>0; i--) {
for (int j = 0; j <=n-2*i; j++) {
if (judge(a,j,i)){
return 2*i;
}
}
}
return 0;
}
/**
* 判断当前字符串是否重复
* @param a 字符串
* @param j 起始位置
* @param i 长度
* @return
*/
private boolean judge(String a, int j, int i) {
for (int k = j; k <j+i; k++) {
if (a.charAt(k)!=a.charAt(k+i)){
return false;
}
}
return true;
}
