14132: 【原4132】LCP

题目

题目描述

author: Lmxyy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4132

Description

在进行完NP-Hard问题研究之后，dhh马上又带着xyy走进了字符串的世界。

dhh首先传授给了xyy一个叫做lcp的东西，所谓lcp即为两个字符串的最长公共前缀。dhh的乒乓球赛奖品除了一张图，还获得了两个字符串，他准备用他们来考考xyy对他所传授的lcp的掌握程度。

xyy：“我肯定全盘掌握了。”

dhh：“那现在我给你这两个字符串，你要立马回答这两个字符串的lcp有多长。”

xyy：“这也太傻了。”

dhh：“那要是我每次还可以修改某个字符串的某个字符呢？”

xyy：“emmmm”

Input Format

第一行两个正整数\(N,M\)，表示\(A\)串和\(B\)串的长度。

第二行一个长度为\(N\)的字符串\(A\)。

第三行一个长度为\(M\)的字符串\(B\)。

接下来一个正整数\(Q\)，表示dhh的修改个数。

接下来\(Q\)行，每行的形式为\(a \quad b \quad c\)

\(a\)的取值为\(0\)或\(1\)，\(0\)表示表示修改\(A\)串，\(1\)表示修改\(B\)串；
\(b\)表示修改位置，保证合法，下标从\(1\)开始；
\(c\)表示修改后的字符。

Output Format

对于每组询问，输出一行一个数，表示答案。

Sample Input 1

6 5
babccb
babcc
4
0 3 a
1 2 c
0 2 c
1 3 a

Sample Output 1

Data Range

对于\(40 \%\)的数据，\(N,M \le1000 \)，\(Q \le 1000\)。

对于\(100 \%\)的数据，\(N,M \le 100000 \)，\(Q \le 200000\)。

字符集大小为所有小写字母。

ligongzzz's solution

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    int len = min(n, m);

    vector<int> lcp(len, 0);
    string A, B;
    cin >> A >> B;

    int cur_pos = 0;
    for (; cur_pos < len && A[cur_pos] == B[cur_pos]; ++cur_pos);
    lcp[0] = cur_pos;

    int q;
    cin >> q;

    for (; q > 0; --q) {
        int a, b;
        char c;
        cin >> a >> b;
        cin.get();
        cin >> c;
        if (b > len)
            continue;
        if (a == 0)
            A[b - 1] = c;
        else
            B[b - 1] = c;

        --b;
        for (cur_pos = 0; lcp[cur_pos] <= b; cur_pos = lcp[cur_pos]);
        if (A[b] != B[b]) {

        }
    }

    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
int tr[2000000],ans[200001],n,m,q,x,y,step,width,p,tmp;//tr代表节点对应区间的LCP
char a[2][200001],ch;
int main() {
    scanf("%d%d",&n,&m);
    scanf("%s",a[0]);
    scanf("%s",a[1]);
    scanf("%d",&q);
    n=min(n,m);
    for (m=1;m<n;m<<=1);
    for (int i=m;i<m+n;++i)
        if (a[0][i-m]==a[1][i-m]) tr[i]=1;
    width=m>>1;
    step=1;
    for (int i=m-1;i>=1;--i)
    {
        if (i<width){step<<=1;width>>=1;}
        if (tr[i<<1]==step) tr[i]=tr[i<<1]+tr[(i<<1)+1];
        else tr[i]=tr[i<<1];
    }
    for (int i=0;i<q;++i)
    {
        scanf("%d%d",&x,&y);
        getchar();
        scanf("%c",&ch);
        a[x][y-1]=ch;
        if (y<=n){
            if (tr[m+y-1]!=(a[0][y-1]==a[1][y-1])) {
                tr[m+y-1]=(a[0][y-1]==a[1][y-1]);
                step = 1;
                p = m + y - 1;
                while ((p >>= 1) > 0) {
                    tmp=tr[p];
                    if (tr[p << 1] == step) tr[p] = tr[p << 1] + tr[(p << 1)|1];
                    else tr[p] = tr[p << 1];
                    if (tr[p]==tmp) break;//若值未更新则不再上溯
                    step <<= 1;
                }
            }
        }
        ans[i]=tr[1];
    }
    for (int i=0;i<q;++i) printf("%d\n",ans[i]);
    return 0;
}