首页 > 其他分享 >CF235C Cyclical Quest

CF235C Cyclical Quest

时间:2024-08-03 12:27:40浏览次数:13  
标签:Cyclical 匹配 int len Quest link CF235C 长度 getchar

题意

给定一个主串\(S\)和\(n\)个询问串,求每个询问串的所有循环同构在主串中出现的次数总和。
相同的循环同构只算一次

题解

sam的其中一个作用就是可以统计某个子串的出现次数,这个很好搞。

我们把询问字符串复制两遍, 设询问串长度为\(m\), 则复制串中所有长度为\(m\)的的子串都是循环同构

对于复制串中的每个位置,我们维护向左的最远匹配,当然这个匹配不用太远,最远到当前这个endpos自身包含长度为\(m\)的串就行

所以匹配过程就是: 初始在1状态,匹配长度为0, 每次向右加入一个字符时,如果上一个状态能转移就转移,使得当前匹配长度加一,否则就不断的跳link,将匹配长度置为\(len[link]\), (这样做没有问题, 对于一个匹配长度和它对应的\(endpos_i\),匹配程度len一定有 \(len_i >= len >len_{i-1}\), 然后对于一个有转移的link,转移后加一, 所以匹配长度为\(link+1\)也没什么问题。

对于每次转移完成,如果当前匹配长度大于等于\(m\),但当前endpos不包含\(m\),我们就不断跳link,并且把匹配长度置为link.len,这也没什么问题,每次转移后,当前endpos应该也是包含匹配长度的?

至于重复的同构,因为所有的同构长度相同,本质相同的同构一定会走到相同的endpos,对于每一个endpos只统计一次答案即可。

实现

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <set>
#define ll long long
using namespace std;

int read(){
	int num=0, flag=1; char c=getchar();
	while(!isdigit(c) && c!='-') c=getchar();
	if(c=='-') flag=-1, c=getchar();
	while(isdigit(c)) num=num*10+c-'0', c=getchar();
	return num*flag; 
}

int readc(){
	char c=getchar();
	while(c<'a' || c>'z') c=getchar();
	return c-'a'; 
}

const int N = 1000500;
int n, m;
char s[N];


namespace sam{
	struct{
		int len, link, siz=0;
		int ch[26];
	}st[N<<1];
	vector<int> ptr[N<<1];
	int las, sz;
	
	void init(){
		las=1, sz=1;
		st[1].len=0, st[1].link=0; 
	}
	
	void extend(int c){
		int cur=++sz, p=las;
		st[cur].len=st[las].len+1, st[cur].siz=1;
		while(p && !st[p].ch[c]) 
			st[p].ch[c]=cur, p=st[p].link;
		
		if(p){
			int nex = st[p].ch[c];
			if(st[p].len+1 == st[nex].len){
				st[cur].link = nex;
			}else{
				int clone = ++sz;
				st[clone].len=st[p].len+1, st[clone].link = st[nex].link;
				for(int i=0; i<26; i++) st[clone].ch[i] = st[nex].ch[i];
				st[cur].link=clone, st[nex].link=clone;
				
				while(st[p].ch[c]==nex) st[p].ch[c]=clone, p=st[p].link;
			}
		}else{
			st[cur].link=1;
		}
		
		las = cur;
	}
	
	void dfsPtr(int x){
		for(int i=0; i<ptr[x].size(); i++) {
			dfsPtr(ptr[x][i]);
			st[x].siz += st[ptr[x][i]].siz;
		}
	}
	
	void buildPtr(){
        // for(int i=1; i<=sz; i++){
        //     for(int j=0; j<26; j++){
        //         if(st[i].ch[j])
        //             printf("%d %d %c\n", i, st[i].ch[j], j+'a');
        //     }
        // }

		for(int i=1; i<=sz; i++) {
			ptr[st[i].link].push_back(i);
			// printf("%d %d %d\n", st[i].link, i, st[i].len); 
		}
		dfsPtr(1);
	}
	

}

string str;
int t[N];

void solve(){
    string str1; cin>>str1;
    m = str1.size();
    for(int i=0; i<2*m; i++){
        t[i] = str1[i%m]-'a';
    }
    set<int> v;

    int x = 1; int y = 0;
    for(int i=0; i<2*m; i++){
        while(true){
            if(sam::st[x].ch[t[i]]){
                x = sam::st[x].ch[t[i]];
                y++;
                break;
            }

            if(x == 1) break;
            x = sam::st[x].link;
            y = sam::st[x].len;
        }

        while(sam::st[sam::st[x].link].len >= m) x = sam::st[x].link, y = sam::st[x].len;

        if(sam::st[x].len >= m && y>=m) {
            if(v.find(x) == v.end()){
                v.insert(x);
            }
        }
    }

    ll ans = 0;
    for(auto i : v){
        ans += sam::st[i].siz;
    }
    printf("%lld\n", ans);

}

int main(){
	cin >> str;
	for(int i=0; i<str.size(); i++){
		s[i+1] = str[i]-'a';
	} n = str.size();
//	for(int i=1; i<=n; i++) s[i]=readc();
	sam::init();
	for(int i=1; i<=n; i++) sam::extend(s[i]); 
    sam::buildPtr();
    
    int T = read();
    while(T--){
        solve();
    }
	
	return 0;
}

标签:Cyclical,匹配,int,len,Quest,link,CF235C,长度,getchar
From: https://www.cnblogs.com/ltdjcoder/p/18340176

相关文章

  • Enhancing Question Answering for Enterprise Knowledge Bases using Large Language
    本文是LLM系列文章,针对《EnhancingQuestionAnsweringforEnterpriseKnowledgeBasesusingLargeLanguageModels》的翻译。使用大型语言模型增强企业知识库的问答能力摘要1引言2相关工作3前言4方法5实验6结论摘要高效的知识管理在提高企业和组......
  • 如何在python中通过requests和opencv加载uint16 png文件
    我正在尝试从URL自动加载图像,然后将其加载到numpy矩阵。为此,我需要使用requests和opencv库。对于像uint8这样编码的标准图像,它以正确的方式工作,并且由于值溢出而损坏了uint16图像。这是我现在正在使用的一个简单的最小代码:importrequestsimportcv2importnumpy......
  • 将 cookie 数据添加到 requests.urlretrieve 中
    我正在尝试从受密码保护的网站下载.torrent文件。我已经成功地使用cookie访问该网站,如下所示:cookies={'uid':'232323','pass':'31321231jh12j3hj213hj213hk','__cfduid':'kj123kj21kj31k23jkl21j321j3kl213kl21j3'}......
  • Cool Request重大更新:可以统计任意方法耗时【送源码】
    什么是CoolRequestCoolRequest是一个IDEA中的接口调试插件,除了可以发起基本的HTTP请求之外,还提供了强大的反射调用能力,可以绕过拦截器,这点广受网友的好评,当然伴随着还有Spring中对@Scheduled注解的调用,以及xxl-job的支持,这是不是很酷(Cool)?什么是Trace我怀着一颗激动的心......
  • Jenkins 远程触发 403 No valid crumb was included in the request
    Jenkins远程触发403Novalidcrumbwasincludedintherequest Jenkins使用curl执行远程触发命令,会报403错误打开如下图  系统管理-》scriptConsole在下面脚本命令行中输入hudson.security.csrf.GlobalCrumbIssuerConfiguration.DISABLE_CSRF_PROTECTION=tr......
  • 60.requests模块
    【一】爬虫初识1)概念爬虫是一种自动化获取互联网数据的技术,通过模拟浏览器行为,向目标网站发送请求并获取响应,然后解析响应中的数据2)工作原理发送HTTP请求,模拟浏览器行为,获取网站的响应,并解析响应中的数据3)分类通用爬虫:对整个互联网进行爬取定向爬虫:只针对特定的网站进......
  • 2.Request,Response和序列化类
    【一】不同编码格式的http请求django视图类或视图函数的request#只针对post请求的urlencoded编码格式才有数据(<QueryDict:{"a":"a"}>)request.POST#请求地址框中获得数据(<QueryDict:{"a":["a"]}>)request.GET #只取一个request.GET.get('key')......
  • vue3 封装request请求
    vue3原生请求封装我这里用一个案例来解释需求:把vue3原生的静态页集成到vue2的若依项目并且可以访问vue2接口在vue3src下的utils下创建文件request.ts文件importaxiosfrom"axios";import{showMessage}from"./status";//引入状态码import{ElMess......
  • 将 JSON 发送到 Flask,request.args 与 request.form
    我的理解是,request.argsFlask中包含来自GET请求的URL编码参数,而request.form包含POST数据。我很难理解为什么在发送POST请求时,尝试使用request.form访问数据会返回400错误,但是当我尝试使用request.args......
  • 如何在 FastAPI 中间件中以不同方式捕获或处理 RequestValidationError 异常?
    如何正确组合RequestValidationError异常处理程序,如:@app.exception_handler(RequestValidationError)asyncdefvalidation_exception_handler(request,exc):response=prepare_response({},g_ERROR__INCORRECT_PARAMS)returnJSONResponse(content=re......