动态规划

字符串

2019-09-28  本文已影响0人  云中翻月

字符串DP

字符串匹配

后缀数组

后缀数组的注意点：
1 两个串拼接在一起。
2 height数组的性质。
POJ 1509: Glass Beads
字符串最小表示法模板题。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
字符串最小表示法模板题。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<string> //不要用cstring 否则会在POJ上CE 
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=2000000+5;
const int INF=0x3f3f3f3f;
int T,n;
char s[maxn];
int cal(char* s) {
    int i=0,j=1,k;
    while(i<n&&j<n) {
        for(k=0; k<n&&s[i+k]==s[j+k]; k++);
        if(k==n) break;
        if(s[i+k]>s[j+k]) {
            i=i+k+1;
            if(i==j) i++;
        } else {
            j=j+k+1;
            if(i==j) j++;
        }
    }
    return min(i,j);
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Glass Beads.in","r",stdin);
    cin>>T;
    while(T--){
        cin>>s;
        n=strlen(s);
//      cout<<n<<endl;
        for(int i=0;i<=n-1;i++) s[i+n]=s[i];
//      for(int i=0;i<=2*n-1;i++) cout<<s[i];
//      cout<<endl;
        cout<<cal(s)+1<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3415: Common Substrings
题意：A与B长度至少为k的公共子串个数。
题目相当于需要求A的所有后缀和B的所有后缀之间的最长公共前缀的长度，并把最长公共前缀长度不小于K的部分全部加起来。
首先将A和B拼起来（中间放一个不可能出现的字符），然后对这个新字符串预处理出sa和h数组。
接下来，对于属于A的后缀i和属于B的后缀j的lcp（h[i+1]到h[j]的最小值），对答案的贡献就是lcp-K+1。
显然，直接枚举i和j的时间复杂度是O(n^{2})。
考虑优化。
假设目前处理到属于B的后缀j，那么就需要统计与前面A的后缀能够组成多少长度不小于K的公共子串。
我们设前面满足条件的A的后缀的个数为cnt，显然lcp的瓶颈就是后缀j和前面cnt个A的后缀对应的h值中的最小值。
因为j的枚举过程为从左向右，所以上述所求的h的值需要满足单调递减的，于是可以用单调栈来维护这个值。
具体地说，我们维护一个h值单调递增的栈，每加入一个属于B的后缀j，就将栈中前面h值大于h[j]的部分删掉。这些删掉的部分就会和后缀j组成lcp=h[j]的数对，从而计算贡献。
对于A的后缀，同样的方法处理一遍即可。
需要注意的是：
1 只有需要统计的（属于不同串）一种后缀的height是有价值的，不需要统计的一种后缀的height需要入栈，但是没有价值。
2 为了保证贡献始终为正数，需要按照h分组，每一组中的h都要大于等于k（因为贡献取决于组内的最小值，所以可以将一组元素全部压缩成一个元素），这样组内产生的数对之间的最小h就一定大于等于k。按照每一块统计即可。
3 不要忘记开longlong。
其他题解链接：https://blog.csdn.net/u013368721/article/details/41852771
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
题意：A与B长度至少为k的公共子串个数。 
题目相当于需要求A的所有后缀和B的所有后缀之间的最长公共前缀的长度，并把最长公共前缀长度不小于K的部分全部加起来。
首先将A和B拼起来（中间放一个不可能出现的字符），然后对这个新字符串预处理出sa和h数组。
接下来，对于属于A的后缀i和属于B的后缀j的lcp（h[i+1]到h[j]的最小值），对答案的贡献就是lcp-K+1。
显然，直接枚举i和j的时间复杂度是O(n^{2})。
考虑优化。
假设目前处理到属于B的后缀j，那么就需要统计与前面A的后缀能够组成多少长度不小于K的公共子串。
我们设前面满足条件的A的后缀的个数为cnt，显然lcp的瓶颈就是后缀j和前面cnt个A的后缀对应的h值中的最小值。
因为j的枚举过程为从左向右，所以上述所求的h的值需要满足单调递减的，于是可以用单调栈来维护这个值。
具体地说，我们维护一个h值单调递增的栈，每加入一个属于B的后缀j，就将栈中前面h值大于h[j]的部分删掉。这些删掉的部分就会和后缀j组成lcp=h[j]的数对，从而计算贡献。 
对于A的后缀，同样的方法处理一遍即可。
需要注意的是：
1 只有需要统计的（属于不同串）一种后缀的height是有价值的，不需要统计的一种后缀的height需要入栈，但是没有价值。 
2 为了保证贡献始终为正数，需要按照h分组，每一组中的h都要大于等于k（因为贡献取决于组内的最小值，所以可以将一组元素全部压缩成一个元素），这样组内产生的数对之间的最小h就一定大于等于k。按照每一块统计即可。 
3 不要忘记开longlong。 
其他题解链接：https://blog.csdn.net/u013368721/article/details/41852771 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5*2+5;
const int INF=0x3f3f3f3f;
int t1[maxn],t2[maxn],sa[maxn],h[maxn],rk[maxn],c[10*maxn],a[maxn];
int m,n;
void calcsa(int n,int m){
    int *x=t1,*y=t2,p=0,f=0;
    for(int i=1;i<=m;i++)c[i]=0;
    for(int i=1;i<=n;i++)c[x[i]=a[i]]++;
    for(int i=1;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i;i--)sa[c[x[i]]--]=i;
    for(int i=1;i<=n&&p<=n;i<<=1){
        p=0;
        for(int j=n-i+1;j<=n;j++)y[++p]=j;
        for(int j=1;j<=n;j++)if(sa[j]>i)y[++p]=sa[j]-i;
        for(int j=1;j<=m;j++)c[j]=0;
        for(int j=1;j<=n;j++)c[x[y[j]]]++;
        for(int i=1;i<=m;i++)c[i]+=c[i-1];
        for(int j=n;j;j--)sa[c[x[y[j]]]--]=y[j];
        swap(x,y);x[sa[1]]=1;p=2;
        for(int j=2;j<=n;j++)
        x[sa[j]]=y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i]?p-1:p++;
        m=p;
    }
    for(int i=1;i<=n;i++)rk[sa[i]]=i;
    for(int i=1;i<=n;i++){
        int j=sa[rk[i]-1];
        if(f)f--;while(a[i+f]==a[j+f])f++;
        h[rk[i]]=f;
    }
}
int K;
char s1[maxn],s2[maxn];
int len1,len2;
ll ans;
struct node{
    int cnt,h;
    ll sum;
}st[maxn];
int top;
void init(){
    n=0;ans=0ll;
}
void solve(){
    top=0; //栈顶指针 
    for(int i=2;i<=n;i++){  
        if(h[i]<K) top=0; //按K分组 
        else{
            int cnt=0;
            while(top&&h[i]<=st[top].h) cnt+=st[top--].cnt; //维护单调递增性 记录后缀i前面比它的h值大的属于A的后缀个数 
            st[++top].cnt=cnt+(sa[i-1]<=len1);
            st[top].h=h[i];
            st[top].sum=top?st[top-1].sum:0;
            st[top].sum+=(ll)(h[i]-K+1)*st[top].cnt;
            if(sa[i]>=len1+1) ans+=st[top].sum;
        }
    }
    top=0;
    for(int i=2;i<=n;i++){
        if(h[i]<K) top=0;
        else{
            int cnt=0;
            while(top&&h[i]<=st[top].h) cnt+=st[top--].cnt; //维护单调递增性 记录后缀i前面比它的h值大的属于B的后缀个数 
            st[++top].cnt=cnt+(sa[i-1]>=len1+1);
            st[top].h=h[i];
            st[top].sum=top?st[top-1].sum:0;
            st[top].sum+=(ll)(h[i]-K+1)*st[top].cnt;
            if(sa[i]<=len1) ans+=st[top].sum;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Common Substrings.in","r",stdin);
    while(scanf("%d",&K)&&K){
        scanf("%s%s",s1,s2);
        init(); 
        len1=strlen(s1),len2=strlen(s2);
        for(int i=0;i<len1;i++) a[++n]=s1[i]-' ';
        a[++n]='$'; //中间填入一个不可能出现的字符 
        for(int i=0;i<len2;i++) a[++n]=s2[i]-' ';
        calcsa(n,10000); //预处理sa和h数组 
        solve();
        printf("%lld\n",ans);
    }
    return 0;
}
#endif
#ifdef method_2
/*
sa模板 
*/
#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int t1[N],t2[N],sa[N],h[N],rk[N],c[10*N],a[N];
char s[N];
int m,n;
void calcsa(int n,int m){
    int *x=t1,*y=t2,p=0,f=0;
    for(int i=1;i<=m;i++)c[i]=0;
    for(int i=1;i<=n;i++)c[x[i]=a[i]]++;
    for(int i=1;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i;i--)sa[c[x[i]]--]=i;
    for(int i=1;i<=n&&p<=n;i<<=1){
        p=0;
        for(int j=n-i+1;j<=n;j++)y[++p]=j;
        for(int j=1;j<=n;j++)if(sa[j]>i)y[++p]=sa[j]-i;
        for(int j=1;j<=m;j++)c[j]=0;
        for(int j=1;j<=n;j++)c[x[y[j]]]++;
        for(int i=1;i<=m;i++)c[i]+=c[i-1];
        for(int j=n;j;j--)sa[c[x[y[j]]]--]=y[j];
        swap(x,y);x[sa[1]]=1;p=2;
        for(int j=2;j<=n;j++)
        x[sa[j]]=y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i]?p-1:p++;
        m=p;
    }
    for(int i=1;i<=n;i++)rk[sa[i]]=i;
    for(int i=1;i<=n;i++){
        int j=sa[rk[i]-1];
        if(f)f--;while(a[i+f]==a[j+f])f++;
        h[rk[i]]=f;
    }
}
int main(){
    scanf("%s",s);int len=strlen(s);
    for(int i=0;i<len;i++)a[++n]=s[i]-' ';
    calcsa(n,10000);
    for(int i=1;i<=n;i++)printf("%d ",sa[i]);
    return 0;
}
#endif
#ifdef method_3

#endif

POJ 3729: Facer’s string
利用height将后缀分组，然后统计每一组内属于第一个串和第二个串分别有多少即可。
注意一定要保证a数组的数字大于等于1。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
利用height将后缀分组，然后统计每一组内属于第一个串和第二个串分别有多少即可。
注意一定要保证a数组的数字大于等于1。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
//const int maxn=50000*2+5;
const int maxn=500000*2+5;
const int maxnum=10000+5;
const int INF=0x3f3f3f3f;
int t1[maxn],t2[maxn],sa[maxn],h[maxn],rk[maxn],c[10*maxn],a[maxn];
int m,n;
void calcsa(int n,int m){
    int *x=t1,*y=t2,p=0,f=0;
    for(int i=1;i<=m;i++)c[i]=0;
    for(int i=1;i<=n;i++)c[x[i]=a[i]]++;
    for(int i=1;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i;i--)sa[c[x[i]]--]=i;
    for(int i=1;i<=n&&p<=n;i<<=1){
        p=0;
        for(int j=n-i+1;j<=n;j++)y[++p]=j;
        for(int j=1;j<=n;j++)if(sa[j]>i)y[++p]=sa[j]-i;
        for(int j=1;j<=m;j++)c[j]=0;
        for(int j=1;j<=n;j++)c[x[y[j]]]++;
        for(int i=1;i<=m;i++)c[i]+=c[i-1];
        for(int j=n;j;j--)sa[c[x[y[j]]]--]=y[j];
        swap(x,y);x[sa[1]]=1;p=2;
        for(int j=2;j<=n;j++)
        x[sa[j]]=y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i]?p-1:p++;
        m=p;
    }
    for(int i=1;i<=n;i++)rk[sa[i]]=i;
    for(int i=1;i<=n;i++){
        int j=sa[rk[i]-1];
        if(f)f--;while(a[i+f]==a[j+f])f++;
        h[rk[i]]=f;
    }
}
int len1,len2;
void init(){
    n=0;
}
//利用height将后缀分组，然后统计每一组内属于第一个串和第二个串分别有多少。
int solve(int k){
    int res=0;
    for(int i=1;i<=n;i++){
        if(h[i]<k) continue; 
        //h[i]>=k  排名为i的后缀与排名为i-1的后缀的最长公共前缀长度>=k 
        int one=0,two=0;
        if(sa[i-1]<=len1) one++;
        if(sa[i-1]>=len1+1) two++;
        for(;i<n,h[i]>=k;i++){ //统计每一组内属于第一个串和第二个串分别有多少
            if(sa[i]<=len1) one++;
            if(sa[i]>=len1+1) two++;
        }
        if(two) res+=one; //只要匹配上了 就有贡献 
    }
    return res;
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Facer’s string.in","r",stdin);
    int k;
    while(scanf("%d%d%d",&len1,&len2,&k)!=EOF){
        init();
        int temp;
        for(int i=1;i<=len1;i++) scanf("%d",&temp),a[++n]=temp+1;//注意一定要保证a数组的数字大于等于1
        a[++n]=maxnum;
        for(int i=1;i<=len2;i++) scanf("%d",&temp),a[++n]=temp+1;
//      for(int i=1;i<=n;i++) D(a[i]);
//      E;
        calcsa(n,maxnum);
//      for(int i=1;i<=n;i++) D(h[i]); //h[i]为排名为i的后缀与排名为i-1的后缀的最长公共前缀 
//      E;
        int ans=solve(k)-solve(k+1); //lcp大于等于k的子串数-lcp大于等于k+1的子串数 
        printf("%d\n",ans);
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif
上一篇 下一篇

猜你喜欢

热点阅读