介紹

子串：串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串
子序列：子序列中的字符在字符串中不一定是連在一起的，而是刪除其中若干個(gè)， 但子序列一定是單調(diào)的
簡單說就是子序列不連續(xù)，子串連續(xù)

序列自動(dòng)機(jī)可以在復(fù)雜度為O（n）下判斷一個(gè)串是不是另一個(gè)串的子序列

序列自動(dòng)機(jī)的本質(zhì)其實(shí)就是空間換時(shí)間，因?yàn)楸┝ψ鐾耆彩强梢缘?#xff0c;但是會(huì)超時(shí)，dp做的話還容易超空間

所需數(shù)組：
next[i][j] ：j的范圍為（0~25）即對(duì)應(yīng)26個(gè)英文字母。表示原串s的第i位后面那26個(gè)字母j出現(xiàn)的最早的位置
也就是next指向的是下一個(gè)j的坐標(biāo)，這樣的話把next的值帶入下一個(gè)next[i][j]中的j，就可以一直向下找

你可以理解成建了一棵樹，一直向外伸長樹枝，相連在一起

那如何建樹呢？
next存的是最早出現(xiàn)的字符，我們可以倒著建，將后面的賦給前面
我們用next[i+1][j]賦給next[i][j],找到第i個(gè)字符后面的26個(gè)字母最早出現(xiàn)的位置
next[i][s[i]-‘a(chǎn)’]=i
然后把當(dāng)前字符更新到當(dāng)前字符在原串中從后向前最晚出現(xiàn)的位置

for (int i = n; i >= 1; i--){for (int j = 0; j < 26; j++) nxt[i][j] = nxt[i + 1][j];int w=str[i]-'a';nxt[i][w] = i;}

查找時(shí)可以這樣：

int now = nxt[i][mark[pos++] - 'a'];while (now != -1 && pos < 10) {now = nxt[now][mark[pos++] - 'a'];}

例題：
例題

總結(jié)

以上是生活随笔為你收集整理的序列自动机的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。