[KMP+乱搞]hdoj 4749

大致题意：

     求文本串中最多能选出多少子串，使得这些子串和模式串匹配。这里匹配的标准是，串中任意两个位置大小关系相同。

 

大致思路：

      对每个位置i求出 0---i中多少个值大于小于等于str[i]并根据这些值去匹配

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=100002;
int n,m,k;
int ttt[nMax],ppp[nMax],sum1[nMax][30],low1[nMax],high1[nMax],sum2[nMax][30],low2[nMax],high2[nMax];

int lent,lenp,next[nMax];

int equal1(int pa,int tb){
    int i;
    if(tb==pa){
        if(high1[tb]==high2[pa]&&low1[tb]==low2[pa]&&sum1[tb][ttt[tb]]==sum2[pa][ppp[pa]])return 1;
        else return 0;
    }else{
        int low=0,high=0,sum=sum1[tb][ttt[tb]]-sum1[tb-pa-1][ttt[tb]];
        for(i=1;i<=k;i++){
            if(i<ttt[tb]){
                low+=sum1[tb-pa-1][i];
            }else if(i>ttt[tb]){
                high+=sum1[tb-pa-1][i];
            }
        }
        if(low1[tb]-low==low2[pa]&&high1[tb]-high==high2[pa]&&sum==sum2[pa][ppp[pa]])return 1;
        else return 0;
    }
}
void get_next(){
    int i,j=-1;
    next[0]=-1;
    for(i=1;i<=lenp;i++){     //pat[j]是不是可以理解为i的前一个字符的next值所指想的字符
        while(j>-1&&ppp[j+1]!=ppp[i])j=next[j];
        if(ppp[j+1]==ppp[i])j++;
        next[i]=j;
    }
}

int KMP(){
    int ans=0,i=0,j=-1,last=-lenp-1;
    get_next();
    for(i=0;i<lent;i++){
        while(j!=-1&&!equal1(j+1,i)){//ppp[j+1]!=ttt[i]
//            cout<<j+1<<" edual1 "<<i<<endl;
            j=next[j];
        }
        if(equal1(j+1,i)){
//            cout<<j+1<<" edual1 "<<i<<endl;
            j=j+1;
        }
        if(j==lenp-1){
            if(i-last>=lenp){
                ans++;  //找到一个匹配/
                last=i;
            }
        }
    }
    return ans;
}

void init(){
    lenp=m,lent=n;
    int i,j;
    memset(low1,0,sizeof(low1));
    memset(low2,0,sizeof(low1));
    memset(high1,0,sizeof(high1));
    memset(high2,0,sizeof(high2));
    memset(sum1,0,sizeof(sum1));
    sum1[0][ttt[0]]=1;
    for(i=1;i<n;i++){
        for(j=1;j<=k;j++){
            sum1[i][j]=sum1[i-1][j];
            if(j<ttt[i]){
                low1[i]+=sum1[i][j];
            }else if(j>ttt[i]){
                high1[i]+=sum1[i][j];
            }
        }
        sum1[i][ttt[i]]++;
    }
    memset(sum2,0,sizeof(sum2));
    sum2[0][ppp[0]]=1;
    for(i=1;i<m;i++){
        for(j=1;j<=k;j++){
            sum2[i][j]=sum2[i-1][j];
            if(j<ppp[i]){
                low2[i]+=sum2[i][j];
            }else if(j>ppp[i]){
                high2[i]+=sum2[i][j];
            }
        }
        sum2[i][ppp[i]]++;
    }
}

int main(){
    int i,j;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        for(i=0;i<n;i++)scanf("%d",&ttt[i]);
        for(i=0;i<m;i++)scanf("%d",&ppp[i]);
        init();
        printf("%d\n",KMP());
    }
    return 0;
}