HDU 4641 至少出现K次本质不同子串数:后缀自动机_k 处不匹配的子串数目-程序员宅基地

技术标签: 后缀自动机  HDU  本质不同子串  

题意:先给出一个串,然后有若干操作。操作1:在结尾续上一个新字符。操作2:查询至少出现了K次的,本质不同的子串个数。


题解:SAM裸题,插入一个新的字符之后,就暴力在parent上转移++,但是也不能那么暴力,我们知道parent链上的num是单调增的,当遇到一个num>=k的点就不需要再继续走了,因为前边的肯定统计到答案里边了。


Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 25e4+1000;
char s[maxn];
int len,k,n,m;
char temp[5];
struct SAM{
	int last,cnt,nxt[maxn*2][26],fa[maxn*2],l[maxn*2],num[maxn*2];
	int ans;
	void init(){
		last = cnt=1;
		memset(nxt[1],0,sizeof nxt[1]);
		fa[1]=l[1]=num[1]=0;
		ans=0;
	}
	int inline newnode(){
		cnt++;
		memset(nxt[cnt],0,sizeof nxt[cnt]);
		fa[cnt]=l[cnt]=num[cnt]=0;
		return cnt;
	}
	void add(int c){
		int p = last;  
        int np = newnode();  
        last = np;  
        l[np] =l[p]+1;  
        while (p&&!nxt[p][c]){  
            nxt[p][c] = np;  
            p = fa[p];  
        }  
        if (!p){  
            fa[np] =1;  
        }else{  
            int q = nxt[p][c];  
            if (l[q]==l[p]+1){  
                fa[np] =q;  
            }else{  
                int nq = newnode();  
                memcpy(nxt[nq],nxt[q],sizeof nxt[q]);  
                fa[nq] =fa[q];  
                num[nq] = num[q];
                l[nq] = l[p]+1;  
                fa[np] =fa[q] =nq;  
                while (nxt[p][c]==q){  
                    nxt[p][c]=nq;  
                    p = fa[p];  
                }  
            }  
        }
		int temp = last;
		while (temp){
			if (num[temp]>=k){
				break;
			}
			num[temp]++;
			if (num[temp]==k){
				ans+=l[temp]-l[fa[temp]];
			}
			temp = fa[temp];
		}  
	}
}sam;
int main(){
	while (scanf("%d%d%d",&n,&m,&k)!=EOF){
		scanf("%s",s);
		len = strlen(s);
		sam.init();
		for (int i=0;i<len;i++){
			sam.add(s[i]-'a');
		}
		while (m--){
			int flag;
			scanf("%d",&flag);
			if (flag==1){
				scanf("%s",temp);
				sam.add(temp[0]-'a');
			}else{
				printf("%d\n",sam.ans);
			}
		}
	}
	return 0;
} 


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/calabash_boy/article/details/78058477

智能推荐

android-----XUtils框架之BitmapUtils加载照片实现_android图片加载bitmap-程序员宅基地

文章浏览阅读5.4k次。作为比较成熟的流行框架,XUtils中的BitmapUtils部分为我们加载照片提供了很大方便,他集成了LRUCache和DiskLruCache缓存机制,在很大程度上避免了我们在加载较多 照片时出现的OOM异常,这篇博客我们从使用的角度学习下BitmapUtils的用法,下一篇将从源码的角度带你真正了解BitmapUtils; 我们使用BitmapUtils实现一个照片墙的功能_android图片加载bitmap

pycharm切换python版本后,No Python at ‘C:\Program Files\Python39\python.exe‘问题消除_no python at 'c:\program files\python39\python.exe-程序员宅基地

文章浏览阅读2.3w次,点赞8次,收藏22次。一,拿到别人的Pycharm脚本运行,发现是基于Python3.8的版本,而自己环境是Python3.9的版本,切换方法见百度经验https://jingyan.baidu.com/article/6d704a136f04ac28db51cad5.html二.pycharm怎么切换python版本,No Python at 'C:\Program Files\Python39\python.exe'问题消除问题描述:原因分析:Porject Interpreter没有设置完全_no python at 'c:\program files\python39\python.exe

【Android Fragment】解决ViewPager嵌套时Fragment的mUserVisibleHint属性不同步的问题-程序员宅基地

文章浏览阅读266次。2017-1-11日更新:setUserVisibleHint中过滤父Fragment未显示的情况上一篇【Android】友盟统计Fragment页面显示隐藏的完美解决方案 我们讲了通过Fragment的mUserVisibleHint属性可以准确的监听Fragment在ViewPager中的显示与隐藏现在新的问题又来了,当ViewPager嵌套ViewPager的时候子ViewPager中F..._viewpager嵌套viewpager fragment setuservisiblehint.

安卓工具类:FileUtils_fileutils 注入-程序员宅基地

文章浏览阅读268次。public class MineFileUtils { /** * 使用本地安装的文件查询器,打卡文件 * * @param activity * @param filepath */ public static void openAndroidFile(Activity activity, String filepath) ..._fileutils 注入

如果有人能力不如你工资比你高怎么看?_比你菜工资比你高-程序员宅基地

文章浏览阅读5.1k次,点赞3次,收藏3次。你在公司里工作,如果同办公室里的一个人,能力没有你强,但工资却高于你,你会不会有想法,心理能平衡吗?1. 错误回答:1) 我当然不平衡,那我还干的什么意思?2) 如果他的能力比我强,我不会有想法。如果没有我强,我肯定心理不平衡。(路健就是这样回答的)3) 如果公司对待员工是这样的不公平,肯定企业文化有问题,这样的公司只有走人。2. 正确回答:(别忘了换位思考原则)工资是员工最敏感的问题,公司一般都会尽量处理好,如果那个同事的能力不如我,工资还高于我,肯定是他在其他方面强于我。或者,他能为公司解决_比你菜工资比你高

获取对话框当前cfont_VC调用系统字体对话框-程序员宅基地

文章浏览阅读474次。1、通过MFC类调用字体对话框2、通过win32API函数调用字体对话框通过MFC类调用字体对话框CFontDialog构造函数CFontDialog(LPLOGFONTlplfInitial=NULL,DWORDdwFlags=CF_EFFECTS|CF_SCREENFONTS,CDC*pdcPrinter=NULL,CWnd*pParentWnd=NULL..._vc++如何获取当前计算中的系统字体

随便推点

ThreadLocal使用-程序员宅基地

文章浏览阅读45次。ThreadLocal的官方API解释为:“该类提供了线程局部 (thread-local) 变量。这些变量不同于它们的普通对应物,因为访问某个变量(通过其get或set方法)的每个线程都有自己的局部变量,它独立于变量的初始化副本。ThreadLocal实例通常是类中的 private static 字段,它们希望将状态与某一个线程(例如,用..._threadlocal 内部有个hashtable

无线干扰的20种错误说法-程序员宅基地

文章浏览阅读222次。随着无线设备的普及以及对于移动应用要求的提高,企业必须勤于管理规划整个部署。而有些已投入使用的或者新兴的无线技术和常用电子设备却影响了无线网络的运行性能。其中RF干扰是最主要的影响无线网络运作的原因,它会影响安全性和无线网络的稳定性。本文罗列了关于无线干扰问题的 20种最普遍的错误说法。错误说法 #1: “唯一的干扰来自于其他的802.11网络。” 802.11设备数不胜数,..._非802.11信号查找

html 指定语言,标记语言——为文字指定CSS样式-程序员宅基地

文章浏览阅读201次。标记语言——为文字指定CSS样式互联网 发布时间:2008-10-17 18:55:59 作者:佚名 我要评论点击这里返回网页教学网 HTML教程 栏目.想浏览CSS教程请点这里。上文:标记语言——CSS布局。Chapter 13 为文字指定样式我想以一章的篇幅来讨论用CSS设定文字样式的做法是个好点子.一般处理文字内容大概是应用CSS最多的地方,就算对没有完全遵守标准点击这里返回脚..._如何给一段文字定义css

配置llama实现impala on yarn-验证未通过,仅以此文作为参考-程序员宅基地

文章浏览阅读1.2k次。以下内容采自网络,目前验证未通过,仅以此作为参考:简介:早期的Impala版本中,为了使用Impala,我们通常会在以Client/Server的结构在各个集群节点启动impala-server、impala-state-store和impala-catalog服务,并且在启动过程中无法动态调整内存和CPU的分配。CDH5之后,Impala开始支持Impala-on-yarn模式,通过一个叫做L..._llama

BZOJ4939: [Ynoi2016]掉进兔子洞(莫队 bitset)-程序员宅基地

文章浏览阅读80次。题意题目链接一个长为 n 的序列 a。有 m 个询问,每次询问三个区间,把三个区间中同时出现的数一个一个删掉,问最后三个区间剩下的数的个数和,询问独立。注意这里删掉指的是一个一个删,不是把等于这个值的数直接删完,比如三个区间是 [1,2,2,3,3,3,3] , [1,2,2,3,3,3,3] 与 [1,1,2,3,3],就一起扔掉了 1 个 1,1 个 2,2 个 3...

soapui 自动化教程(三)_soapui nosr换行显示-程序员宅基地

文章浏览阅读4.6k次,点赞6次,收藏9次。soapui 之 groovy 进阶上一节讲到如何使用groovy脚本执行用例。def testStep = TEST_SUITE.getTestCaseByName('TestSuite').getTestStepByName('login')def testStepContext = new WsdlTestRunContext(testStep)def result = testStep._soapui nosr换行显示