一個字符串的子串是字符串中連續(xù)的一個序列爪飘，而一個字符串的子序列是字符串中保持相對位置的字符序列，譬如嘲玫，"adi"可以使字符串"abcdefghi"的子序列但不是子串悦施。這也就決定了在解這兩種"LCS"問題上的一些區(qū)別。
Longest-Common-Substring和Longest-Common-Subsequence是不一樣的去团。
之前我寫的時候這兩個概念有錯誤抡诞，見諒。
把子序列改成字串后條件更嚴苛了土陪，某些情況下解題的復雜度也低一些昼汗。
回文子串
比如drabfbaz里面abfba就是回文的，長度為5.
思路1：逐個字母判斷
我們以每個字母為中心鬼雀，逐個判斷字符兩邊的回文長度顷窒。
由于比較簡單，就不多說了：
//solution1: make i as center and extends
int solution1(char* s)
{
int n=strlen(s);
int i=0,j=0;
int curmax=0,max=0;
for(i=0;i<n;i++)
{
for(j=0;i-j>=0&&i+j<n;j++)//j is the length of substr
{
//odd length
if(s[i+j]!=s[i-j])
break;
curmax=j*2+1;
}
if(curmax>max)
max=curmax;
for(j=0;i-j>=0&&i+j+1<n;j++)//j is the length of substr
{
//even length:
if(s[i-j]!=s[i+j+1])
break;
curmax=j*2+2;
}
if(curmax>max)
max=curmax;
}
return max;
}
解法2：manacher算法
參考：https://www.felix021.com/blog/read.php?2040
我們上面的解法分了奇數(shù)長度和偶數(shù)長度兩種情況討論，并且復雜度也不低鞋吉，我們嘗試著改進一下：
首先鸦做，我們解決奇數(shù)和偶數(shù)：我們在字符串里面插入#號后看看發(fā)生了什么：
abbc->#a#b#b#a# abdba->#a#b#d#b#a#
這樣所有的都變成了奇數(shù)長度，就可以統(tǒng)一處理了谓着。我們還可以在字符串首加入另一個符號比如$來將字符串的下標0轉換為更熟悉的下標1泼诱。
以字符串12212321為例，經(jīng)過上一步赊锚，變成了 S[] = "$#1#2#2#1#2#3#2#1#";
然后用一個數(shù)組 P[i] 來記錄以字符S[i]為中心的最長回文子串向左/右擴張的長度（包括S[i]治筒，也就是把該回文串“對折”以后的長度），比如S和P的對應關系：
S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
(p.s. 可以看出舷蒲，P[i]-1正好是原字符串中回文串的總長度）所以我們的問題轉化為耸袜，如何計算
p[i]的值我們來發(fā)現(xiàn)一條規(guī)律，來從一定程度上簡化計算：
假如我們位置為id的地方牲平，其長度為p[id]堤框，記右邊界為mx=id+p[id];
(實際上是mx-1吧）
那么其左邊界就是id-p[id]假設有一個位置i，其正好在id這個字符為中心的回文字符串里面
(i<mx)纵柿，那么根據(jù)回文的對稱性胰锌，其左邊會有一個與之對稱的位置j，j=2*id-i藐窄；
那么這個能干什么呢资昧？因為我們是從左往右邊求的，所以直接可以得到右邊位置i的最小回文長度荆忍！
因為回文的對稱性格带，左邊的長度如果是x的話，且j-x>mx的對稱點刹枉，即位置j的回文子串全部在以id為中心的字符串里面的話叽唱，可以推出以i為中心的回文字符串的長度最小也是j的回文長度p[j]；但是如果j的回文字符串超出了mx對稱點的邊界微宝，也可以說棺亭，p[i]的值最少為
mx-i得到上述兩種情況的最小長度后，我們再對位置i的字符進行判斷蟋软，是否有更長的字符滿足回文镶摘。
這些思路轉化為代碼就是：
for(i = 1; s[i] != '\0'; i++)
{
p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
while(s[i + p[i]] == s[i - p[i]])
p[i]++;
if(i + p[i] > mx)
{
mx = i + p[i];
id = i; }
}
把之前的內容整理下：
- 預處理字符串的函數(shù)：
char c[1000];
int func(char* s)
{
if (!s)
return NULL;
int n = strlen(s);
c[0] = '$';
int i = 0, j = 1;
while (i < n)
{
c[j++] = '#';
c[j++] = s[i++];
}
c[j] = '#';
return j;
}
主干：
int solution_manacher(char* s)
{
if (!s)
return 0;
int len = func(s);//length of c
int i = 1;
int curmax = 0;
int p[1000];//p[i] is the length of ith char in c
p[0] = 0;
int id=1 , mx = 0;//mx=id+p[id],but id=????????
for (i = 1; i<len; i++)
{
p[i] = 1;
//if (mx>i)
// p[i] = minTwo(mx - i, p[2 * id - i]);//actually pi>=minTwo
//else p[i] = 1;//one char,itself
if (mx > i)
{
p[i] = p[2 * id - i];
if (mx - i < p[i])
p[i] = mx - i;
}
while (c[i + p[i]] == c[i - p[i]])
p[i]++;
if (i + p[i]>mx)
{
mx = i + p[i];
id = i;
}
if (p[i]>curmax)
curmax = p[i];
}
return curmax-1;
}
最長公共子串
由于這個情況限制只能是連續(xù)的，所以情況要簡單一些岳守，方程也退化為：
思路和上次差不多凄敢，也是創(chuàng)建了一個二維數(shù)組：
#include <iostream>
int lcsubstr(char* s1, char* s2)
{
if (!s1 || !s2)
return 0;
int len1 = strlen(s1);
int len2 = strlen(s2);
int i = 0, j = 0;
int max=0;
int a[100][100];
memset(a, 0, sizeof(a));
for (i = 0; i < len1; i++)
{
for (j = 0; j < len2; j++)
{
if (s1[i] == s2[j])
a[i + 1][j + 1] = 1+a[i][j];//careful! i+1&j+1
if (a[i + 1][j + 1]>max)
max = a[i + 1][j + 1];
}
}
return max;
}
int main()
{
char s1[] = "abcd";
char s2[] = "bcdef";
std::cout << lcsubstr(s1, s2);
}
不知道有沒有bug額。湿痢。
