KMP的正确使用法_x新疆网络赛Query on a string

题意，给定一个大字符串，给定一个小模式串，定义两种不同的任务模式，分别是查询和更改：

查询对应区间内，有多少个匹配到位的数字；

修改某一位的某一个字母。

于是直觉告诉我们是KMP，而且需要一个单点更新，动态查询的数据结构——直觉上认为树状数组比较合适执行这个任务。

于是，开个大大数组，保存每次匹配时对应位的四字母的匹配指针的位置。

每次扫描到了模式串长度都往树状数组里面存入相关元素。

每次修改之后应当从新就地走一遍模式串，更新相关内容，注意，每次匹配到的新的结果和老结果向同的时候就应当退出。

#include<bits/stdc++.h>

using namespace std;

const long long MAXN=;

char str[MAXN];

char str2[];

int lenOfSub;

int flags[MAXN];

int f[MAXN];

int n,m;

int tree[MAXN];

void insert(int pos,int key)

{

    pos+=;

    while(pos<MAXN)

    {

        tree[pos]+=key;

        pos+=pos&(-pos);

    }

}

int getSum(int pos)

{

    pos+=;

    int ret=;

    while(pos)

    {

        ret+=tree[pos];

        pos-=pos&(-pos);

    }return ret;

}

void get_fail()

{

    int len=strlen(str2);

    lenOfSub=len;

    f[]=f[]=;

    for(int i=;i<len;++i)

    {

        int j=f[i];

        while(j&&str2[i]!=str2[j])j=f[j];

        f[i+]= str2[i]==str2[j]? j+:;

    }

}

void get_match()

{

    int j=f[];

    int len=strlen(str);

    for(int i=;i<len;++i)

    {

        while(j&&str[i]!=str2[j])j=f[j];

        j= str[i]==str2[j]? j+:;

        flags[i]=j;

    }

//    for(int i=0;i<len;++i)cout<<flags[i]<<ends;

//    cout<<endl;

}

void init()

{

    scanf("%d\n",&n);

    memset(tree,,sizeof(tree));

    memset(f,,sizeof(f));

    gets(str);

    gets(str2);

    get_fail();

    get_match();

    int len=strlen(str);

    for(int i=;i<len;++i)

    {

        if(flags[i]==lenOfSub)insert(i,);

    }

    for(int it=;it<n;++it)

    {

        char cm[];

        scanf("%s",cm);

        if(cm[]=='Q')

        {

            int pos1;int pos2;

            scanf("%d%d",&pos1,&pos2);pos1--;pos2--;

            int poss=-;int j=f[];

                int ans=;

            for(int i=pos1;i<=pos2;++i)

            {

                while(j&&str[i]!=str2[j])j=f[j];

                j= str[i]==str2[j]? j+:;

                if(j==lenOfSub)ans++;

                if(j==flags[i])

                {

                    poss=i;

                    break;

                }

            }

            if(poss==-)

            {

                cout<<ans<<"\n";

            }else

            {

                cout<<ans+(getSum(pos2)-getSum(poss))<<"\n";

            }

        }else

        {

            int pp;

            scanf("%d%s",&pp,cm);

            pp--;

            str[pp]=cm[];

            int j=;

            if(pp)j=flags[pp-];

            for(int i=pp;i<len;++i)

            {

                while(j&&str[i]!=str2[j])j=f[j];

                j= str[i]==str2[j]? j+:;

                if(flags[i]==j)break;

                if(flags[i]==lenOfSub)insert(i,-);

                if(j==lenOfSub)insert(i,);

                flags[i]=j;

            }

        }

    } 

    cout<<"\n";

}

int main()

{

    cin.sync_with_stdio(false);

    int t;

    scanf("%d",&t) ;

    while(t--)init();

    return ;

}

巴特西

KMP的正确使用法_x新疆网络赛Query on a string

最新文章

热门文章