2024.3.28

2024.3.28 【浮世景色百千年依旧，人之在世却如白露与泡影。】

Thursday 二月十九

<theme = oi-"string">

今天神奇模拟赛）

A. 水水题

题目描述

给定若干个串，对于每个串，求出所有可能的串使得这些可能的串既是原串的前缀又是原串的后缀。

输入格式
若干行，表示若干个原串

输出格式
若干行，每行从小到大输出所有可能的长度
样例输入

ababcababababcabab
aaaaa

样例输出

2 4 9 18
1 2 3 4 5

数据规模与约定
对于100%的数据，串的个数 ≤10，每个串长度小于400000。

//2024.3.28
//by white_ice
#include <bits/stdc++.h>
using namespace std;
#define itn int
const int oo = 1000006;

char st[oo];
int len,nextv[oo];
itn out[oo];

signed main(){
    ios::sync_with_stdio(0);
    cout.tie(0);

while(scanf("%s",st)!=EOF){
    len = strlen(st);

    itn i=0,j=-1;
    nextv[0]=-1;

    while(i<len)
        if(j==-1||st[j]==st[i])
            nextv[++i]=++j;
        else j = nextv[j];

    itn ned=len,cnt=1;

    while(nextv[ned]) out[cnt++]=nextv[ned],ned = nextv[ned];
    cnt--;

    for(int i=cnt;i>0;i--)
        cout << out[i] << ' ';
    cout << len << endl;
}
    return 0;
}

B. 第二章 圆锥曲线与方程

题目描述

小草翻开了数学选修2-1的第二章《圆锥曲线与方程》，突然想到一道题。数学书的某一页上写着两行字，分别是两个字符串，记为 S 和 T，它们都非空且只由小写字母组成。

小草发现，如果 S 中出现了 T，即 S 中出现了 T 这个子串，是很难看的。

此时小草就会用手上的小圆锥盖掉 S 中的一些字母（一个小圆锥只能盖掉一个字母，被盖去的字母两边的字母不会相连，相当于 S 断成左右两截），使得最后不存在 S 的一个子串是 T。

因为小圆锥是从数学老师那里偷来的，所以小草希望尽可能少地用它来盖住字母，要不然被老师发现之后可能会被开更多的白条。

但是小草正陷于一道解析几何丧题，没有时间来考虑这个问题，因此希望你能帮帮忙。作为回报，小草会把那道解析几何丧题让给你来做。

输入格式
第一行一个字符串 S， 第二行一个字符串 T

输出格式
输出最少需要多少个小圆锥。

样例输入

lylylylyily
lyl

样例输出

2

数据规模与约定
样例所示数据的一种覆盖方案是分别盖住第3和第7个字母，变成lyylyyily（*表示被小圆锥覆盖的位置）。

对于 10% 的数据，|S|,|T|≤5。

对于 20%的数据，|S|,|T|≤10。

对于 40%的数据，|S|≤10^3,|T| ≤30

对于 60%的数据，|T| ≤30

在后 40% 的数据中，存在 10%的数据，|T|=1

在后 40% 的数据中，存在另外 10% 的数据，S 中的字母全部都是一样的。

对于 100% 的数据，|S|≤10^5,|T|≤104

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int n,m,nxt[N],ans;
string p,s;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>s>>p;
	s='0'+s;
	p='0'+p;
	n=p.size()-1;
	m=s.size()-1;
	for(int i=2,j=0;i<=n;++i){
		while(j&&p[i]!=p[j+1])j=nxt[j];
		if(p[i]==p[j+1])++j;
		nxt[i]=j;
	}
	for(int i=1,j=0;i<=m;++i){
		while(j&&s[i]!=p[j+1])j=nxt[j];
		if(s[i]==p[j+1])++j;
		if(j==n){
			++ans;
			j=0;
		}
	}
	cout<<ans<<endl;
	return 0;
}

感谢zzh同学提供的代码）

C. Find

题目描述

我们定义两种操作

操作1的格式 ：I 字符串S，加入1个字符串S

操作2的格式 ：F字符串S,查找字符串S是否在当前寻找前已经出现过

注释：同一个字符串可能多次被插入和查找，字符串S长度≤20。

输入格式
第一行 指令个数N 接下来N行每行一个指令。

输出格式
对于每次查找，找到输出'YES'，没找到输出'NO'。

样例输入

10
I abcdef
I abcdef
F abcdef
F abcd
I ef
F fff
F ef
F abcdef
I asd
F assd

样例输出

YES
NO
NO
YES
YES
NO

数据规模与约定

对于 40%的数据 N≤5000

对于 100% 的数据 N≤150000

//2024.3.28
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn int

map<string,bool> q;
int n;
char c,a[30];

int main(){
    scanf("%d",&n);
    for (itn i=1;i<=n;i++){
        scanf("%s%s",&c,&a);
        string s = a;
        switch(c){
            case 'I':
                q[s] = true;
                break;
            case 'F':
                //cout << q[s] << ' ';
                puts(q[a]?"YES":"NO");
                break;
        }
    }
    return 0;
}

这个题告诉我们，能用STL就要用，胆大一点。