企业网站策划方案书,网络公司排名100名,深圳市房地产信息系统平台,十大电商代运营公司排名正题
ybtoj KMP-4 题目大意
给出字符串S#xff0c;问你有多少个子串满足ABA的形式#xff0c;且∣A∣⩾k,∣B∣⩾1|A|\geqslant k,|B|\geqslant 1∣A∣⩾k,∣B∣⩾1 解题思路
可以先枚举左端点#xff0c;然后跑KMP#xff0c;使其满足左右两个A#xff0c;然后判断A,…正题
ybtoj KMP-4 题目大意
给出字符串S问你有多少个子串满足ABA的形式且∣A∣⩾k,∣B∣⩾1|A|\geqslant k,|B|\geqslant 1∣A∣⩾k,∣B∣⩾1 解题思路
可以先枚举左端点然后跑KMP使其满足左右两个A然后判断A,B是否满足条件然后计算答案
时间复杂度O(n2)O(n^2)O(n2)理论上是过不了的但它就是过了题解还是这么写的 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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(s1); 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, s1, k);n strlen(s1);for (int i 0; i n - k * 2; i)kmp(s i);printf(%d, ans);return 0;
}
