当前位置: 首页 > article >正文

「2.2」Radio Transmission

 

「2.2」Radio Transmission

题目描述

给你一个字符串,它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的,现在只想知道它的最短长度是多少。

输入格式

第一行给出字符串的长度 L,第二行给出一个字符串,全由小写字母组成。

输出格式

输出最短的长度。

样例输入1

8
cabcabca

样例输出1

3

注释说明

样例说明
对于样例,我们可以利用 abc 不断自我连接得到 abcabcabc,读入的 cabcabca 是它的子串。

数据范围与提示
对于全部数据,1≤L≤10^6。

//i%(i-next[i])==0&&next[i]!=0 ,
//则字符串前i位循环,
//而且循环节长度:i-next[i],
//循环次数: i/( i-next[i])
#include <bits/stdc++.h>
using namespace std;
int n,ne[1000003],np,ns;
string s,p;
int main() {
	cin>>np;
	cin>>p;
	p=" "+p;
	for(int i=1,j=0; i<np; i++){
		while(j&&p[i+1]!=p[j+1])j=ne[j];
		if(p[j+1]==p[i+1])j++;
		ne[i+1]=j;
		//cout<<j;
	}
	cout<<np-ne[np]<<"\n";

}

/*
cabcabcaa

*/

 


http://www.kler.cn/a/281429.html

相关文章:

  • 【Docker】docker的简介与部署方法
  • SIMCom芯讯通A7680C发起HTTP通讯:在UI串口进行模拟;代码调用API操作
  • TDengine数据恢复TAOSD出错时退出时的解决方法
  • MinIO中object_name是什么
  • JavaScript 文件上传详解与实现
  • 使用Python调用JavaScript进行网页自动化操作
  • AI引领,驱动未来:零售企业的新质生产力革命
  • Java 5.3 - MyBatis
  • USB:物理接口
  • 监控摄像头内存卡格式化了怎么恢复?
  • Dockerfile、docker run和docker-compose的区别
  • 【人工智能】项目案例分析:使用LSTM生成图书脚本
  • C#高效内存管理:运用对象池与结构体优化技术
  • 制造业如何利用MES管理系统实现数据采集
  • vscode运行已编译好的程序
  • 更改了ip地址怎么改回来
  • 完整的模型训练路线
  • 【精选】基于django柚子校园影院(咨询+解答+辅导)
  • Scrapy入门学习
  • Java基础——自学习使用(泛型)