当前位置： 首页 > news >正文

【后缀自动机】ZOJ3891、HDU5343

news 来源：原创 2024/5/4 20:33:46

ZOJ3891 K-hash

出处：ZOJ Monthly, July 2015 - K

题意：给出一个整数K(<=32)和一个长度50000以内由十进制数构成的字符串S，要求统计S的不重复子串所表示的数对K取模的结果。

思路：在SAM上按节点拓扑序DP，dp[x][i]表示x节点处取模后结果为i的方案数。

　　　当x节点处接受字符c可转移到y时，枚举i(0<=i<k)，可以得到方程：dp[y][(i*10+c)%k] = sigma{ dp[x][i] | tans[x][c]=y }

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <limits>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define x first
#define y second
#define sf scanf
#define pf printf
#define vec vector
#define pb push_back
#define mp make_pair
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define clr(a,b) memset(a,b,sizeof(a))
#define bin_cnt(x) __builtin_popcount(x)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define srep(sub,s) for(int sub=s&(s-1);sub;sub=(sub-1)&s)
#define irep(i,a) for(__typeof(a.begin()) i=a.begin();i!=a.end();i++)
#define irrep(i,a) for(__typeof(a.rbegin()) i=a.rbegin();i!=a.rend();i++)
#define inf numeric_limits<int>::max()
#define finf numeric_limits<double>::infinity()
#define eps 1e-8
#pragma GCC optimize ("O3")
#define o3 __attribute__((optimize("O3")))
#pragma comment(linker, "/STACK:32505856")

template<class T> inline T sqr(T a) {return a*a;}
template<class T> inline void gmin(T&a,T b) {if(a>b)a=b;}
template<class T> inline void gmax(T&a,T b) {if(a<b)a=b;}
inline int dcmp(const double &a) {return a>eps?1:(a<-eps?-1:0);}
struct Initializer{Initializer(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}}initializer;

int K;
ll ans[32];

struct SAM {
  #define N 50005
  int tot,last;
  int go[N<<1][10],pre[N<<1],step[N<<1];
  int chr[N<<1],din[N<<1];
  ll dp[N<<1][32];

  inline void new_node(int s) {
    step[++tot]=s;
    pre[tot]=0;
    din[tot]=0;
    clr(go[tot],0);
    clr(dp[tot],0);
  }

  inline void build(char *s) {
    tot=0,last=1;
    new_node(0);
    chr[tot]=0;
    int n=strlen(s);
    rep(i,0,n-1) {
      new_node(step[last]+1);
      int c=s[i]-'0';
      chr[tot]=c;
      int p=last,np=tot,q,nq;
      for (;p&&!go[p][c];p=pre[p]) go[p][c]=np;
      if (!p) pre[np]=1;
        else {
          q=go[p][c];
          if (step[q]==step[p]+1) pre[np]=q;
            else {
              new_node(step[p]+1), nq=tot;
              chr[tot]=c;
              rep(j,0,9) go[nq][j]=go[q][j];
              pre[nq]=pre[q];
              pre[np]=pre[q]=nq;
              for (;p&&go[p][c]==q;p=pre[p]) go[p][c]=nq;
            }
        }
      last=np;
    }
  }

  void solve() {
    clr(ans,0);
    dp[1][0]=1;

    queue<int> q;
    rep(i,1,tot) rep(j,0,9) if (go[i][j]) din[go[i][j]]++;
    rep(i,1,tot) if (!din[i]) q.push(i);

    while (sz(q)) {
      int i=q.front();

      rep(j,0,9) if (go[i][j]) {
        if (!--din[go[i][j]]) {
          q.push(go[i][j]);
        }
        if (i==1 && j==0) continue;
        rep(k,0,K-1) {
          dp[go[i][j]][(k*10+j)%K] += dp[i][k];
        }
      }
      rep(k,0,K-1) ans[k]+=dp[i][k];

      q.pop();
    }
  }
} sam;


int main() {
  static char s[N];
  while (~sf("%s%d",s,&K)) {
    sam.build(s);
    sam.solve();
    ans[0]-=string(s).find('0')==string::npos;
    rep(i,0,K-1) pf("%lld%s",ans[i],i<K-1?" ":"\n");
  }
  return 0;
}

 

HDU5343 MZL's Circle Zhou

出处：2015 Multi-University Training Contest 5 - 1001

题意：依次给出长度90000以内的A、B两串，求将A的子串与B的子串按顺序拼接能得到的不重复的串的个数。

思路：A、B两串分别建两个SAM处理，先将B串翻转，利用SAM(B)求以字符c结尾（开头）的子串个数。

　　　对于SAM(A)中节点x，若x不能接受字符c，则将B串中以c开头的子串“接”在其后，构成Asub+Bsub的形式。

　　　详见官方题解 http://blog.sina.com.cn/s/blog_15139f1a10102vokk.html

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <limits>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define x first
#define y second
#define sf scanf
#define pf printf
#define vec vector
#define pb push_back
#define mp make_pair
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define clr(a,b) memset(a,b,sizeof(a))
#define bin_cnt(x) __builtin_popcount(x)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define srep(sub,s) for(int sub=s&(s-1);sub;sub=(sub-1)&s)
#define irep(i,a) for(__typeof(a.begin()) i=a.begin();i!=a.end();i++)
#define irrep(i,a) for(__typeof(a.rbegin()) i=a.rbegin();i!=a.rend();i++)
#define inf numeric_limits<int>::max()
#define finf numeric_limits<double>::infinity()
#define eps 1e-8
#pragma GCC optimize ("O3")
#define o3 __attribute__((optimize("O3")))
#pragma comment(linker, "/STACK:32505856")

template<class T> inline T sqr(T a) {return a*a;}
template<class T> inline void gmin(T&a,T b) {if(a>b)a=b;}
template<class T> inline void gmax(T&a,T b) {if(a<b)a=b;}
inline int dcmp(const double &a) {return a>eps?1:(a<-eps?-1:0);}
struct Initializer{Initializer(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}}initializer;

struct SAM {
  #define N 90009
  int tot,last;
  int go[N<<1][26],pre[N<<1],step[N<<1];
  int chr[N<<1];

  inline void new_node(int s) {
    step[++tot]=s;
    pre[tot]=0;
    clr(go[tot],0);
  }

  inline void build(char *s) {
    tot=0,last=1;
    new_node(0);
    int n=strlen(s);
    rep(i,0,n-1) {
      new_node(step[last]+1);
      int c=s[i]-'a';
      chr[tot]=c;
      int p=last,np=tot,q,nq;
      for (;p&&!go[p][c];p=pre[p]) go[p][c]=np;
      if (!p) pre[np]=1;
        else {
          q=go[p][c];
          if (step[q]==step[p]+1) pre[np]=q;
            else {
              new_node(step[p]+1), nq=tot;
              chr[tot]=c;
              rep(j,0,25) go[nq][j]=go[q][j];
              pre[nq]=pre[q];
              pre[np]=pre[q]=nq;
              for (;p&&go[p][c]==q;p=pre[p]) go[p][c]=nq;
            }
        }
      last=np;
    }
  }
} sam;

#define ull unsigned long long
char a[N],b[N];
ull dp[26];

int main() {
  int T;
  sf("%d",&T);
  while (T--) {
    sf("%s%s",a,b);
    clr(dp,0);

    reverse(b,b+strlen(b));
    sam.build(b);
    rep(i,1,sam.tot) {
      dp[sam.chr[i]]+=sam.step[i]-sam.step[sam.pre[i]];
    }

    ull ans=0;
    sam.build(a);
    rep(i,1,sam.tot) {
      ans+=(ull)sam.step[i]-sam.step[sam.pre[i]];
      rep(c,0,25)
        if (!sam.go[i][c])
          ans+=(ull)(sam.step[i]-sam.step[sam.pre[i]])*dp[c];
    }
    cout<<ans+1<<endl;
  }
  return 0;
}

 

两道题均围绕不重复子串的数量展开询问，很容易联想到使用后缀自动机求解。

以前做过较长时间的SAM专题并进行过总结，但时间久远差不多都忘了，正好借机重温一下。

转载于:https://www.cnblogs.com/AlpcFlagship/p/4705144.html

相关文章：

  • linux下一个C语言要求CPU采用
  • how hard to say goodbye to you
  • [hdu4622 Reincarnation]后缀数组
  • I学霸官方免费教程三十二：Java集合框架之Set集合
  • Spark RDD Operations（1）
  • XE3随笔7：可以省略的双引号
  • Cocos2d-x 2.3.3版本 FlappyBird
  • LeetCode Implement Stack using Queues
  • Web前端学习-第六课ＨＴＭＬ篇
  • C# 跨线程呼叫控制
  • (13)[Xamarin.Android] 不同分辨率下的图片使用概论
  • Unity3d之流光效果
  • mysql 的 存储结构（储存引擎）
  • DP_ural_Metro
  • 手把手教你整合 SpringMvc+Spring+MyBatis+Maven
  • Apache Spark Streaming 使用实例
  • express + mock 让前后台并行开发
  • HomeBrew常规使用教程
  • iOS帅气加载动画、通知视图、红包助手、引导页、导航栏、朋友圈、小游戏等效果源码...
  • JDK 6和JDK 7中的substring（）方法
  • learning koa2.x
  • ReactNativeweexDeviceOne对比
  • Redis提升并发能力 | 从0开始构建SpringCloud微服务(2)
  • Redis学习笔记 - pipline（流水线、管道）
  • Sequelize 中文文档 v4 - Getting started - 入门
  • 订阅Forge Viewer所有的事件
  • 欢迎参加第二届中国游戏开发者大会
  • 回流、重绘及其优化
  • 技术：超级实用的电脑小技巧
  • 看图轻松理解数据结构与算法系列(基于数组的栈)
  • 聊聊hikari连接池的leakDetectionThreshold
  • 三分钟教你同步 Visual Studio Code 设置
  • 使用Swoole加速Laravel(正式环境中)
  • 首页查询功能的一次实现过程
  • 关于Kubernetes Dashboard漏洞CVE-2018-18264的修复公告
  • 如何用纯 CSS 创作一个货车 loader
  • ​RecSys 2022 | 面向人岗匹配的双向选择偏好建模
  • #Ubuntu（修改root信息）
  • (2)Java 简介
  • （二十三）Flask之高频面试点
  • (非本人原创)我们工作到底是为了什么？​——HP大中华区总裁孙振耀退休感言（r4笔记第60天)...
  • （全部习题答案）研究生英语读写教程基础级教师用书PDF|| 研究生英语读写教程提高级教师用书PDF
  • （顺序）容器的好伴侣 --- 容器适配器
  • (原創) 如何將struct塞進vector? (C/C++) (STL)
  • (转)Java socket中关闭IO流后，发生什么事？（以关闭输出流为例） .
  • .NET 5种线程安全集合
  • .NET CF命令行调试器MDbg入门（四） Attaching to Processes
  • .Net Core与存储过程(一)
  • .Net Remoting(分离服务程序实现) - Part.3
  • .net 生成二级域名
  • .net中我喜欢的两种验证码
  • @converter 只能用mysql吗_python-MySQLConverter对象没有mysql-connector属性’...
  • @Transactional 竟也能解决分布式事务？
  • [20190113]四校联考
  • [BUG] Hadoop-3.3.4集群yarn管理页面子队列不显示任务