为什么不对啊
查看原帖
为什么不对啊
1164692
lijianACE楼主2024/12/3 22:21

不知道为什么不对,求帮忙!

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
char str[N],p[N];
int nex[N],pos[N],ans[N];
int top=0,lens,lenp;
void getnext(char s[],int len){
  nex[0]=0,nex[1]=0;
  int i=1,j=0;
  while(i<=len){
    if(j==0){
      j++;
      i++;
    }
    if(s[i]==s[j]){
        nex[i]=j;
        i++;
        j++;
      }
    else{
      j=nex[j];
    }
  }
}
void KMP(){
  int j=1,i=1;
  while (i<=lens){
    ans[++top]=i;
    while (j!=0&&str[i]!=p[j]){
     j=nex[j]; 
    }
    j++;
    pos[i]=j;
    if(j==lenp+1){
      top-=lenp;
      j=pos[ans[top]];
    }
    i++;
  }
}
int main() {
  scanf("%s",str+1);
  lens=strlen(str+1);
  scanf("%s",p+1);
  lenp=strlen(p+1);
  getnext(p,lenp);
  KMP();
  for (int i=1;i<=top;i++){
   printf("%c",str[ans[i]]); 
  }
  return 0;
}
2024/12/3 22:21
加载中...