正題

ybtoj KMP-4

---

題目大意

給出字符串S，問你有多少個子串滿足ABA的形式，且$|A|?k,|B|?1$

---

解題思路

可以先枚舉左端點(diǎn)，然后跑KMP，使其滿足左右兩個A，然后判斷A,B是否滿足條件，然后計算答案

時間復(fù)雜度$O(n^2)$，理論上是過不了的，但它就是過了，題解還是這么寫的

---

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 15010 using namespace std; int k, n, ans, nx[N]; char s[N]; void kmp(char* s) {int n = strlen(s+1); nx[1] = 0;for (int i = 2, j = 0; i <= n; ++i){while (s[i] != s[j + 1] && j) j = nx[j];if (s[i] == s[j + 1]) j++;nx[i] = j;}for (int i = 2, j = 0; i <= n; ++i){while (s[i] != s[j + 1] && j) j = nx[j];if (s[i] == s[j + 1]) j++;if (i - j <= j) j = nx[j];//|B|?0if (j >= k) ans++;}return; } int main() {scanf("%s%d", s+1, &k);n = strlen(s+1);for (int i = 0; i < n - k * 2; ++i)kmp(s + i);printf("%d", ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【KMP】子串拆分（ybtoj KMP-4）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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