AcWing 3823. 寻找字符串
原题链接
困难
作者:
术
,
2021-08-30 13:39:01
,
所有人可见
,
阅读 286
1.ON 做法,使用数组存res是否出现过,注意st的使用和 **\0截断字符串**
#include <iostream>
#include <string.h>
using namespace std;
const int N=1e6+5;
int T;
char s[N];
int nexts[N];
bool st[N];
int n;
//第一长next[n],第二长next[next[n]]......
void get_next(int ne[],char str[],int len)
{
for(int i=2,j=0; i<=len; i++)
{
while(j&&str[i]!=str[j+1])
j=ne[j];
if(str[i]==str[j+1])
j++;
ne[i]=j;
}
}
int main()
{
cin>>T;
while(T--)
{
cin>>s+1;
n=strlen(s+1);
get_next(nexts,s,n);
for(int i=0;i<=n;i++) st[i]=false;
for(int i=1;i<n;i++) st[nexts[i]]=true;
int res=0;
for(int i=nexts[n];i;i=nexts[i])
if(st[i]){
res=i;
break;
}
if(!res) cout<<"not exist"<<endl;
else {
s[res+1]='\0';
cout<<s+1<<endl;
}
}
//cout << "Hello world!" << endl;
return 0;
}
2.
#include <iostream>
#include <string.h>
using namespace std;
const int N=1e6+5;
int T;
char s[N];
int nexts[N];
int nextp[N];
int n;
//第一长next[n],第二长next[next[n]]......
void get_next(int ne[],char str[],int len)
{
for(int i=2,j=0; i<=len; i++)
{
while(j&&str[i]!=str[j+1])
j=ne[j];
if(str[i]==str[j+1])
j++;
ne[i]=j;
}
}
int main()
{
cin>>T;
while(T--)
{
cin>>s+1;
n=strlen(s+1);
get_next(nexts,s,n);
bool flag=false;
int res=nexts[n];
while(res)
{
for(int i=2; i<n; i++)
{
if(nexts[i]==res)
{
flag=true;
break;
}
}
if(flag) break;
res=nexts[res];
}
if(flag)
{
for(int i=1; i<=res; i++)
cout<<s[i];
cout<<endl;
}
else
cout<<"not exist"<<endl;
}
//cout << "Hello world!" << endl;
return 0;
}