【浮*光】#字符串# 字符串の相关练习题

#include <cmath>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#define R register

/*【p3290】围棋 // 轮廓线DP + 容斥思想 + KMP
每个格子可以是黑、白、空，求n*m的棋盘上包含‘给定的2*c模板块’的方案数。*/

/*【分析】考虑容斥，ans=3^(n*m)-不含2*c的方案数。
设f[i][j][S][x][y]表示填到了(i,j)，
轮廓线上每个位置作为末尾、是否完全匹配第一个串的状态为S，
与第一个串kmp到了x，与第二个串kmp到了y的方案数。 */

void reads(int &x){ //读入优化（正负整数）
    int fx_=1;x=0;char ch_=getchar();
    while(ch_<‘0‘||ch_>‘9‘){if(ch_==‘-‘)fx_=-1;ch_=getchar();}
    while(ch_>=‘0‘&&ch_<=‘9‘){x=x*10+ch_-‘0‘;ch_=getchar();}
    x*=fx_; //正负号
}

const int mod=1000000007; int i,j,k,c,S,x,y;

int T,n,m,nxt[9],ta[9][3],tb[9][3],na,nb,U,E;

int f[1024][6][6],g[1024][6][6],ans; char a[9],b[9];

int id(char x){ if(x==‘B‘) return 0; return (x==‘W‘)?1:2; }

void up(int&x,int y){ x+=y; if(x>=mod) x-=mod; }

void clear(){ for(S=0;S<U;S++) for(x=0;x<c;x++) for(y=0;y<c;y++) g[S][x][y]=0; }

void copy(){ for(S=0;S<U;S++) for(x=0;x<c;x++) for(y=0;y<c;y++) f[S][x][y]=g[S][x][y]; }

int main(){
    reads(n),reads(m),reads(c),reads(T); //T:模板的数量
    while(T--){ scanf("%s%s",a+1,b+1);
        
        for(i=1;i<=c;i++) a[i]=id(a[i]),b[i]=id(b[i]);
        
        for(nxt[1]=j=0,i=2;i<=c;nxt[i++]=j) //模板第一行自我匹配
         { while(j&&a[j+1]!=a[i]) j=nxt[j]; if(a[j+1]==a[i]) j++; }
        
        for(na=nxt[c],i=0;i<c;i++) 
          for(j=0;j<3;j++){ for(k=i;k&&a[k+1]!=j;k=nxt[k]); 
            if(a[k+1]==j) k++; ta[i][j]=k; }
        
        for(nxt[1]=j=0,i=2;i<=c;nxt[i++]=j) //模板第二行自我匹配
         { while(j&&b[j+1]!=b[i]) j=nxt[j]; if(b[j+1]==b[i]) j++; }

        for(nb=nxt[c],i=0;i<c;i++) 
          for(j=0;j<3;j++){ for(k=i;k&&b[k+1]!=j;k=nxt[k]); 
            if(b[k+1]==j) k++; tb[i][j]=k; }
        
        U=1<<(m-c+1); //匹配的状态
        
        for(S=0;S<U;S++) for(x=0;x<c;x++) for(y=0;y<c;y++) f[S][x][y]=0;

        for(f[0][0][0]=i=1;i<=n;i++){ clear();
            for(S=0;S<U;S++) for(x=0;x<c;x++) for(y=0;y<c;y++)
                if(f[S][x][y]) up(g[S][0][0],f[S][x][y]); copy();
            for(j=1;j<=m;j++){ clear(); for(S=0;S<U;S++) 
              for(x=0;x<c;x++) for(y=0;y<c;y++) if(f[S][x][y]) 
                for(k=0;k<3;k++){ E=S; if(j>=c) if(S>>(j-c)&1) E^=1<<(j-c);
                  int A=ta[x][k]; if(A==c) E|=1<<(j-c),A=na;
                  int B=tb[y][k]; if(B==c){ if(S>>(j-c)&1) continue; B=nb; }
                  up(g[E][A][B],f[S][x][y]); } copy();
            }
        } for(ans=1,i=n*m;i;i--) ans=3LL*ans%mod;

        for(S=0;S<U;S++) for(x=0;x<c;x++) for(y=0;y<c;y++)
            up(ans,mod-f[S][x][y]); printf("%d\n",ans);
    }
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;

/*【p4341】外星联络
求所有出现次数>1的子串出现的次数，子串按照字典序排序。 */

/*【后缀数组】先求出sa和height数组，然后枚举。
由于字符串有一个性质：字符串的所有子串就是所有后缀的所有前缀。
可以枚举每个字符向后延续的长度。然后向右循环，看有多少个height大于该长度。
需要注意：(1)枚举长度时要从height+1开始，因为前面的都已经处理过。
         (2)循环时不能向左循环，因为左边的已经找过。
最后判断一下出现次数是否大于1即可。 */

void reads(int &x){ //读入优化（正负整数）
    int fx=1;x=0;char s=getchar();
    while(s<‘0‘||s>‘9‘){if(s==‘-‘)fx=-1;s=getchar();}
    while(s>=‘0‘&&s<=‘9‘){x=(x<<3)+(x<<1)+s-‘0‘;s=getchar();}
    x*=fx; //正负号
}

const int N=500019; int n,m; char ss[N];

int rank[N],b[N],sa[N],tp[N],tax[N],height[N];

void qsort(){
    for(int i=0;i<=m;i++) tax[i]=0;
    for(int i=1;i<=n;i++) tax[rank[i]]++;
    for(int i=1;i<=m;i++) tax[i]+=tax[i-1];
    for(int i=n;i>=1;i--) sa[tax[rank[tp[i]]]--]=tp[i];
}

void get_height(){ 
    int k=0; //求height[]
    for(int i=1;i<=n;i++){
        if(k) k--; int j=sa[rank[i]-1];
        while(ss[i+k]==ss[j+k]) k++; height[rank[i]]=k; 
    }
}

void get_sa(){
    for(int i=1;i<=n;i++) rank[i]=ss[i]-‘0‘+1,tp[i]=i;
    m=127; qsort(); //第一次基数排序
    for(int k=1;k<=n;k<<=1){
        int p=0; for(int i=n-k+1;i<=n;i++) tp[++p]=i;
        for(int i=1;i<=n;i++) if(sa[i]>k) tp[++p]=sa[i]-k;
        qsort(); for(int i=1;i<=n;i++) // swap(rank,tp);
            b[i]=tp[i],tp[i]=rank[i],rank[i]=b[i]; rank[sa[1]]=p=1;
        for(int i=2;i<=n;i++)
            rank[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]
                &&tp[sa[i]+k]==tp[sa[i-1]+k])?p:++p;
        if(p>=n) break; m=p;
    } get_height();
}

int main(){
    scanf("%d%s",&n,ss+1); get_sa();
    for(int i=2;i<=n;i++){ //按排名枚举子串(第一个舍去)  
        for(int j=height[i-1]+1;j<=height[i];j++){
            //j初始值为‘排名为i-1的子串lcp‘,要<=当前子串串长 
            int k=i; while(height[k]>=j) k++;
            //↑↑寻找lcp值>=j的子串最后一次出现的位置
            printf("%d\n",k-i+1); //重复出现的次数
        }
    }
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;

const int maxn = 5000019;

char ch[3000];

int son[maxn][2],sz[maxn],tot=1,n;

inline void ins(const char*ch){
    int rt=1;
    for(;*ch;++ch){
        int&x=son[rt][*ch-48];
        if(!x) x=++tot;
        ++sz[rt=x];
    }
}

inline void dfs(int rt){
    if(sz[rt]>1) cout << sz[rt] << ‘\n‘;
    if(son[rt][0]) dfs(son[rt][0]);
    if(son[rt][1]) dfs(son[rt][1]); }
    
int main(){ cin >> n >> ch; for(int i=0;i<n;++i)ins(ch+i); dfs(1); }