字串小筆記

紀錄一些好玩的字串判斷方法

判斷遞增子序列

判斷遞增子序列的方法,假設當前字串為
2,5,7,8,9,2,3,4,3,1 此時可以發線子序列可以拆分為
1. 2,5,7,8,9 length = 5
2. 2,3,4 length = 3
3. 3 length = 1
4. 1 length = 1
因此就可以發現相鄰的遞增子序列為 min(length=5,length=3)
而兩個遞增子序列屬於同一個遞增段的話最大長度則為 $\lfloor \frac{cnt}{2} \rfloor$
因此要求長度即

for(int i=0;i<nums.size();i++){
    cnt++; // record the current string length 
    if(i == nums.size()-1 || nums[i] >= nums[i-1]){ // 1. 判斷是否到尾 2. 判斷是否為嚴格遞增序列即a1 > a2
        ans = max({ans,cnt,min(pre,cnt)}); // pre 為上個遞增子序列的長度
        pre = cnt;
        cnt = 0; // 重設
    }
    return ans;
}

LCS

KMP