AC
2026-11-10 20:22:22
发布于:浙江
2阅读
0回复
0点赞
!!!非常简单,谁都会!!!
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100005; // S的最大长度
const int MAXM = 1005; // P的最大长度
string s;
int n, m;
// 计算KMP的next数组 (failure function)
void computeLPSArray(string pat, int M, int* lps) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
// pre_pos[i] 存储模式串前缀长度为i时,在文本串中最早出现的结束位置 (0-indexed)
// 如果不存在,设为 -1
int pre_pos[MAXM];
// suf_pos[i] 存储模式串后缀长度为i时,在文本串中最晚出现的开始位置 (0-indexed)
// 如果不存在,设为 -1
int suf_pos[MAXM];
void solve_for_pattern(string p) {
int len_p = p.length();
// 初始化
for(int i=0; i<=len_p; ++i) {
pre_pos[i] = -1;
suf_pos[i] = -1;
}
// 1. 正向匹配,求前缀的最早结束位置
// 使用 KMP
int lps[MAXM];
computeLPSArray(p, len_p, lps);
int j = 0; // index for pattern
for (int i = 0; i < n; i++) { // index for text s
while (j > 0 && s[i] != p[j]) {
j = lps[j - 1];
}
if (s[i] == p[j]) {
j++;
}
// 如果当前匹配长度为 j,且这是该长度第一次出现(最早),则记录
// 注意:我们要找的是长度为 k 的前缀。当 j=k 时,说明 s[i-k+1 ... i] 匹配 p[0...k-1]
// 结束位置是 i。
if (j > 0) {
// 只有当 pre_pos[j] 还没有被赋值时,才赋值,保证是最早的
if (pre_pos[j] == -1) {
pre_pos[j] = i;
}
}
if (j == len_p) {
j = lps[j - 1];
}
}
// 优化 pre_pos:
// 如果长度为 i 的前缀最早结束于 pos,那么长度为 i-1 的前缀肯定也在 pos 之前或同位置结束吗?
// 不一定。但是,如果长度为 i 的前缀能匹配,说明长度为 i-1 的前缀也能在更早或相同的地方匹配。
// 实际上,我们需要的是:对于任意长度 k,只要存在一个结束位置 <= X 即可。
// 更准确的逻辑是:pre_pos[k] 应该单调不减吗?
// 如果 pre_pos[k] 是 earliest end index for prefix of length k.
// 如果 pre_pos[k] != -1, 则 pre_pos[k-1] 肯定也不为 -1 (除非 k=0),且 pre_pos[k-1] <= pre_pos[k] - 1 ?
// 其实不需要这么复杂,我们只需要确保 pre_pos[k] 是有效的。
// 但是,为了后续判断 pre[j] < suf[len-j],我们需要 pre[j] 尽可能小。
// 上面的 KMP 过程已经保证了 pre_pos[j] 是该长度前缀第一次完全匹配时的结束位置,也就是最小的结束位置。
// 2. 反向匹配,求后缀的最晚开始位置
string rev_s = s;
string rev_p = p;
reverse(rev_s.begin(), rev_s.end());
reverse(rev_p.begin(), rev_p.end());
computeLPSArray(rev_p, len_p, lps);
j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && rev_s[i] != rev_p[j]) {
j = lps[j - 1];
}
if (rev_s[i] == rev_p[j]) {
j++;
}
if (j > 0) {
// 在反转串中,匹配长度为 j,意味着原串中后缀长度为 j 匹配成功。
// 在反转串 rev_s 中,匹配结束于 i,对应原串 s 的开始位置为 n - 1 - i。
// 我们要找最晚的开始位置,即在反转串中最早的结束位置?
// 不,"最晚的开始位置" 意味着在原串 s 中靠右。
// 在原串 s 中靠右 -> 在反转串 rev_s 中靠左 (索引小)。
// 所以,如果在反转串中第一次匹配到长度 j 时,对应的原串开始位置是最大的吗?
// 让我们理清坐标:
// Rev_S index i corresponds to S index n-1-i.
// Match of length j in Rev_S ending at i means Rev_S[i-j+1 ... i] matches Rev_P[0...j-1].
// This corresponds to S[n-1-i ... n-1-(i-j+1)] = S[n-1-i ... n-i+j-2] matching P's suffix.
// The start position in S is n-1-i.
// We want the LATEST start position in S, which means the SMALLEST index in Rev_S?
// No. Latest start position in S -> Largest index in S.
// Largest index in S -> Smallest index in Rev_S.
// So we want the FIRST time we match length j in Rev_S?
// If we match at Rev_S index i1 and later at i2 (i1 < i2),
// Start pos in S for i1 is n-1-i1.
// Start pos in S for i2 is n-1-i2.
// Since i1 < i2, n-1-i1 > n-1-i2.
// So the first occurrence in Rev_S gives the LATEST start position in S.
if (suf_pos[j] == -1) {
suf_pos[j] = n - 1 - i;
}
}
if (j == len_p) {
j = lps[j - 1];
}
}
// 3. 检查分割点
// 前缀长度 j 从 1 到 len_p - 1
for (int j = 1; j < len_p; ++j) {
int suffix_len = len_p - j;
if (pre_pos[j] != -1 && suf_pos[suffix_len] != -1) {
// pre_pos[j] 是前缀在 S 中的结束下标
// suf_pos[suffix_len] 是后缀在 S 中的开始下标
// 要求不重叠且顺序正确:End_Prefix < Start_Suffix
if (pre_pos[j] < suf_pos[suffix_len]) {
cout << 1 << endl; // 这里的输出逻辑由主函数控制,这里只返回是否找到
return;
}
}
}
cout << 0 << endl; // 未找到
}
int main() {
// 优化IO
ios::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> s)) return 0;
n = s.length();
cin >> m;
int ans = 0;
while (m--) {
string p;
cin >> p;
// 如果模式串长度为1,无法分成两个非空子串,直接跳过或判否
if (p.length() < 2) {
// 题目要求 a<=b < c<=d,意味着两段都非空,总长度至少为2
continue;
}
// 我们需要一个函数返回 bool,这里为了简单直接修改逻辑
// 重新封装一下逻辑以便统计 ans
int len_p = p.length();
vector<int> local_pre(len_p + 1, -1);
vector<int> local_suf(len_p + 1, -1);
// --- Forward KMP for Prefixes ---
vector<int> lps(len_p, 0);
// Compute LPS
{
int len = 0;
int i = 1;
while (i < len_p) {
if (p[i] == p[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) len = lps[len - 1];
else { lps[i] = 0; i++; }
}
}
}
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && s[i] != p[j]) j = lps[j - 1];
if (s[i] == p[j]) j++;
if (j > 0 && local_pre[j] == -1) {
local_pre[j] = i; // Earliest end position for prefix of length j
}
if (j == len_p) j = lps[j - 1];
}
// --- Backward KMP for Suffixes ---
string rev_s = s;
string rev_p = p;
reverse(rev_s.begin(), rev_s.end());
reverse(rev_p.begin(), rev_p.end());
// Recompute LPS for reversed pattern
vector<int> lps_rev(len_p, 0);
{
int len = 0;
int i = 1;
while (i < len_p) {
if (rev_p[i] == rev_p[len]) {
len++;
lps_rev[i] = len;
i++;
} else {
if (len != 0) len = lps_rev[len - 1];
else { lps_rev[i] = 0; i++; }
}
}
}
j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && rev_s[i] != rev_p[j]) j = lps_rev[j - 1];
if (rev_s[i] == rev_p[j]) j++;
if (j > 0 && local_suf[j] == -1) {
// j is length of matched suffix.
// Match ends at i in rev_s.
// Start position in original s is n - 1 - i.
// Since we iterate i from 0 to n-1, the first time we hit a specific j
// gives the smallest i, which means the largest start position in s.
local_suf[j] = n - 1 - i;
}
if (j == len_p) j = lps_rev[j - 1];
}
bool found = false;
for (int k = 1; k < len_p; ++k) {
int pref_len = k;
int suff_len = len_p - k;
if (local_pre[pref_len] != -1 && local_suf[suff_len] != -1) {
if (local_pre[pref_len] < local_suf[suff_len]) {
found = true;
break;
}
}
}
if (found) ans++;
}
cout << ans << endl;
return 0;
}
这里空空如也







有帮助,赞一个