一帧数据 Zookeeper安装 CGLib动态代理 properties 分布式 Apache Pivot教程 reactjs curl inheritance casting Fries vue组件开发 npm安装vue photoshop cs3 教程 click事件 两个正态分布相乘 java多行注释 linux查找文件内容 svn安装后右键不显示 pythonsocket编程 mysql插入 python3网络编程 python变量定义 python入门例子 python字符串匹配 python的lambda函数 java基本类型 java类方法 java日期转时间戳 猫爪 ** 相机权限 din字体下载 ad19 矩阵分析与应用 listpreference extjs视频教程 msn格式 teraterm 一键隐藏
当前位置: 首页 > 学习教程  > 编程语言

序列自动机

2020/9/19 14:48:41 文章标签:

一道CF的简单例题
题目链接
nex数组记录第i个位置后j第一次出现的位置。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+500;
string a;
string b;
int nex[N][30];
int main() {
	cin>>a;
	//序列自动机代码
	int n=a.size();
	for(int i=n; i>0; i--) {
		for(int j=0; j<26; j++) nex[i-1][j]=nex[i][j];
		nex[i-1][a[i-1]-'a']=i;
	}
	int m;
	scanf("%d",&m);
	while(m--) {
		cin>>b;
		int cut=0;
		int falg=0;
		for(int i=0; i<b.size(); ++i) {
			if(nex[cut][b[i]-'a']>cut&&nex[cut][b[i]-'a']) {
				cut=nex[cut][b[i]-'a'];
				falg++;
				cout<<b[i];
			} else break;
		}
		if(!falg)cout<<"IMPOSSIBLE";
		cout<<endl;
	}
	return 0;
}

转一篇大佬博客链接,仅供自己参考。
大佬博客链接


本文链接: http://www.dtmao.cc/news_show_200194.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?