SQL Server 字串最大遞增子序列查詢 (CTE 遞迴 + 窗口函數)

給定僅含小寫字母 a-z 的字串 (如 'abcbklmnodfghijkmer')，尋找字典序連續遞增的最長子字串。本文展示 SQL Server 2005+ 相容的 CTE 遞迴解法，並提供 2012+ 窗口函數優化版本。

解題思路

1. 將字串拆解為單字元資料列，附上序號 (id)
2. 遞迴比較相鄰字元：若 前一字元 <= 當前字元 則計數器 +1，否則歸 1
3. 找出計數器最大值及其對應結尾位置，反推起始位置與長度
4. SUBSTRING 截取原字串對應區段

完整查詢 (SQL Server 2005 相容)

DECLARE @vtext VARCHAR(255) = 'abcbklmnodfghijkmer';

/* 1. 字串拆列 + 序號 */
WITH x0 AS (
  SELECT number AS id, SUBSTRING(@vtext, number, 1) AS letter
  FROM master.dbo.spt_values
  WHERE type = 'P' AND number BETWEEN 1 AND LEN(@vtext)
),
/* 2. 遞迴計算遞增長度 */
x1 (id, letter, clen) AS (
  SELECT id, letter, 1 FROM x0 WHERE id = 1
  UNION ALL
  SELECT x0.id, x0.letter,
         CASE WHEN x1.letter <= x0.letter THEN x1.clen + 1 ELSE 1 END
  FROM x0 JOIN x1 ON x0.id = x1.id + 1
)
/* 3. 取最大長度對應區段 */
SELECT SUBSTRING(@vtext, start_pos, max_len) AS 最大遞增子序列
FROM (
  SELECT 
    id, clen,
    MAX(clen) OVER () AS max_len,
    id - MAX(clen) OVER () + 1 AS start_pos
  FROM x1
) t
WHERE clen = max_len;

執行結果

最長遞增子序列為 dfghijkm (長度 8)，對應原字串第 11~18 字元。

SQL Server 2012+ 窗口函數優化版 (無需遞迴 CTE)

DECLARE @vtext VARCHAR(255) = 'abcbklmnodfghijkmer';

WITH chars AS (
  SELECT 
    ROW_NUMBER() OVER (ORDER BY (SELECT 0)) AS id,
    SUBSTRING(@vtext, number, 1) AS letter
  FROM master.dbo.spt_values
  WHERE type = 'P' AND number BETWEEN 1 AND LEN(@vtext)
),
grp AS (
  SELECT 
    id, letter,
    SUM(CASE WHEN LAG(letter) OVER (ORDER BY id) <= letter THEN 0 ELSE 1 END) 
      OVER (ORDER BY id) AS grp_id
  FROM chars
),
len AS (
  SELECT grp_id, COUNT(*) AS cnt, MIN(id) AS start_id
  FROM grp GROUP BY grp_id
)
SELECT TOP 1 SUBSTRING(@vtext, start_id, cnt) AS 最大遞增子序列
FROM len ORDER BY cnt DESC, start_id;

關鍵技巧解析

• master.dbo.spt_values (type='P') 是系統內建的數字輔助表，0~2047 可直接當序號來源
• 遞迴 CTE 中 x0.id = x1.id + 1 實現逐列自我 JOIN，模擬迴圈
• MAX(clen) OVER () 為無分區窗口聚合，取全域最大值並廣播到每列
• 窗口函數版利用 LAG 取前值、條件求和產生分組 ID、再分組統計長度，效能遠優於遞迴

應用延伸

同樣邏輯可套用於：股票連漲天數、連續登入天數、感測器數值連續上升區間等「連續遞增片段」分析場景。