我就是想纪念一下这个写了快一小时的模拟
问题 D: 单词谜
题目描述
有一种英文字谜游戏，一开始创作者选一个称为“根”的单词 R，然后可能多次打乱 R，连接到 R 单 词后面。例如：bbabababb，是根单词 bba，与乱序单词 bab、abb 连接组成。
字谜参加者要面对一个字符串，找出最短的“根”单词。如果找不到输出-1。
输入
第 1 行：长度不超过 100,000 的小写英文字母组成的字符串。
输出
最短的根单词（是输入字符串的前缀）。如果找不到根单词，输出-1。
样例输入 Copy
【样例1】
aaaa
【样例2】
ab
【样例3】
bbabab
样例输出 Copy
【样例1】
a
【样例2】
-1
【样例3】
bba
题意： 找一个最短的前缀使得字符串能够被分成若干份该前缀（可以更改字母的顺序）
思路 ： 枚举前缀的长度，要注意必须要分成若干份前缀才符合题意。可以根据每个字母出现的次数来判断是否符合题意
#include<bits/stdc++.h> #define cutele main using namespace std; const int N = 1e6+7; string s; char ch[N]; int a[26],b[26]; int cutele(){ cin>>ch; s=ch; int n=strlen(ch); bool flag=false; for(int i=1;i<n;i++){ if(s[i]!=s[0]){ flag=true; break; } } if(!flag){ cout<<s[0]<<endl; return 0; } flag=false; for(int i=2;i<n;i++) if(n%i==0){ memset(a,0,sizeof a); flag=true; string last=s.substr(0,i); for(int w=0;w<last.size();w++) a[last[w]-'a']++; for(int j=i;j<n;j+=i){ string now=s.substr(j,i); memset(b,0,sizeof b); for(int k=0;k<now.size();k++) b[now[k]-'a']++; bool flag2=true; for(int q=0;q<26;q++) if(a[q]!=b[q]){ flag2=false; break; } if(!flag2){ flag=false; break; } } if(flag){ cout<<s.substr(0,i)<<endl; return 0; } } if(!flag) puts("-1"); return 0; }
萌新报道，欢迎指正~
