题解：P5256 [JSOI2013] 编程作业

大写字母 A-Z 表示关键字、常量等非变量符号，必须精确匹配，小写字母 a-z 表示变量名，匹配时只需要满足变量名的替换关系一致。

我们需要判断两个字符串在变量名替换意义下是否等价。关键在于：对于每个变量名（小写字母），它在当前位置与上一次出现的位置的距离应该相同。

对于每个位置，如果是大写字母，直接记录其负值，这样既可以比较是否相等，还不用考虑大小写冲。

如果是小写字母，记录该字母距离上一次出现的位置的距离（如果是第一次出现，距离就是当前位置）。

然后跑 kmp，对于大写字母必须精确相等，对于小写字母需要满足相同的距离关系。

时间复杂度是

O(|S| + |T|)

，与标准 KMP 算法相同。

代码实现：

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5, M = 35;
int q, n, m, nxt[N], a[N], b[N], w[M];
string s, t;
inline bool check(int a, int b, int c){
    if(a == b) return true;
    return a > c && b > c;
}
inline void init(){
    for(int i = 0; i <= 27; i++) w[i] = 0;
}
inline int kmp(){
    int res = 0;
    for(int i = 2, j = 0; i <= m; i++){
        while(j && !check(b[j + 1], b[i], j)) j = nxt[j];
        if(check(b[j + 1], b[i], j)) j++;
        nxt[i] = j;
    }
    for(int i = 1, j = 0; i <= n; i++){
        while(j && !check(b[j + 1], a[i], j)) j = nxt[j];
        if(check(b[j + 1], a[i], j)) j++;
        if(j == m) res++, j = nxt[m];
    }
    return res;
}
inline void solve(){
    nxt[1] = 0;
    cin >> s >> t;
    s = " " + s, t = " " + t, n = s.size() - 1, m = t.size() - 1;
    init();
    for(int i = 1; i <= n; i++){
        if(s[i] < 'a') a[i] = -(s[i]);
        else a[i] = i - w[s[i] - 'a' + 1], w[s[i] - 'a' + 1] = i;
    }
    init();
    for(int i = 1; i <= m; i++){
        if(t[i] < 'a') b[i] = -(t[i]);
        else b[i] = i - w[t[i] - 'a' + 1], w[t[i] - 'a' + 1] = i;
    }
    cout << kmp() << "\n";
    return ;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> q;
    while(q--) solve();
    return 0;
}

题解：P5256 [JSOI2013] 编程作业

文章操作

代码实现：

相关推荐

评论

题解：P5256 [JSOI2013] 编程作业