这里母串赋值和算长度不要变，固定模板
int nt[100005][26]; char a[100005]; scanf("%s",a+1); void init() { int len=strlen(a+1); for(int i=len; i>=1; i--) { for(int j=0; j<26; j++) { nt[i-1][j]=nt[i][j]; } nt[i-1][a[i]-'a']=i; } }
判断代码
char b[1005]; scanf("%s",b); int len=strlen(b); int p=0,f=0; for(int i=0; i<len; i++) { p=nt[p][b[i]-'a']; if(p==0) { f=1; break; } } if(f) { cout<<"不是子序列"<<endl; } else { cout<<"是子序列"<<endl; }
例题
https://nanti.jisuanke.com/t/38232
#include<iostream> #include<string.h> using namespace std; char a[100005]; int nt[100005][26]; void init() { int len=strlen(a+1); for(int i=len; i>=1; i--) { for(int j=0; j<26; j++) { nt[i-1][j]=nt[i][j]; } nt[i-1][a[i]-'a']=i; } } int main() { scanf("%s",a+1); int t; scanf("%d",&t); init(); while(t--) { char b[1005]; scanf("%s",b); int len=strlen(b); int p=0,f=0; for(int i=0; i<len; i++) { p=nt[p][b[i]-'a']; if(p==0) { f=1; break; } } if(f) { cout<<"不是子序列"<<endl; } else { cout<<"是子序列"<<endl; } } }
