有没有做淘宝首页特效的网站,网站开发前景咋样,wordpress支付下载地址,招聘页面设计介绍
子串#xff1a;串中任意个连续的字符组成的子序列称为该串的子串 子序列#xff1a;子序列中的字符在字符串中不一定是连在一起的#xff0c;而是删除其中若干个#xff0c; 但子序列一定是单调的 简单说就是子序列不连续#xff0c;子串连续
序列自动机可以在复杂…介绍
子串串中任意个连续的字符组成的子序列称为该串的子串 子序列子序列中的字符在字符串中不一定是连在一起的而是删除其中若干个 但子序列一定是单调的 简单说就是子序列不连续子串连续
序列自动机可以在复杂度为On下判断一个串是不是另一个串的子序列
序列自动机的本质其实就是空间换时间因为暴力做完全也是可以的但是会超时dp做的话还容易超空间
所需数组 next[i][j] j的范围为0~25即对应26个英文字母。表示原串s的第i位后面那26个字母j出现的最早的位置 也就是next指向的是下一个j的坐标这样的话把next的值带入下一个next[i][j]中的j就可以一直向下找
你可以理解成建了一棵树一直向外伸长树枝相连在一起
那如何建树呢 next存的是最早出现的字符我们可以倒着建将后面的赋给前面 我们用next[i1][j]赋给next[i][j],找到第i个字符后面的26个字母最早出现的位置 next[i][s[i]-‘a’]i 然后把当前字符更新到当前字符在原串中从后向前最晚出现的位置 for (int i n; i 1; i--){for (int j 0; j 26; j) nxt[i][j] nxt[i 1][j];int wstr[i]-a;nxt[i][w] i;}查找时可以这样 int now nxt[i][mark[pos] - a];while (now ! -1 pos 10) {now nxt[now][mark[pos] - a];}例题 例题
