9.11 ~ 9.16 훈련 집 --- 비교적 중요, kmp 편

kmp, 다른 문자열 과 같은 부분의 알고리즘 을 빠르게 구 합 니 다. 이번 주 에 조금 배 웠 습 니 다. 먼저 붙 이 고 다음 주 에 더 깊이 배 워 야 합 니 다. 대체적인 사고: 예비 처리 모드 접두사 접두사, 모든 접두사 가 최대 접두사 와 일치 합 니 다. (알 기 어렵 습 니 다. 기본적으로 폭력 이 일치 할 때 특정한 문자 가 다 를 때 이동 해 야 할 최대 거리 입 니 다)일치 하 는 패턴 문자열 에서 가장 긴 접두사 와 접 두 사 를 찾 아 이동 하여 겹 치 게 합 니 다.핵심 코드 (기본적으로 오 선생님 의 코드 를 강제로 외 우 는 것...) 1. 예비 처리 코드, 각 위치 문 자 를 일치 시 키 는 데 실 패 했 습 니 다. 오른쪽으로 이동 해 야 할 최대 거 리 는 p [] 배열 이 존재 합 니 다.

void getp(int n)
{int i,j;
 p[0]=-1;
 j=-1;//     ,                   
 for(i=1;i<=n;i++)
  {while(j>=0&&s1[j+1]!=s1[i])
   {j=p[j];//   ,   ,      ,         ,       
   }
   j++;//         ++
   p[i]=j;//  
  }
  for(i=1;i<=n;i++)
  //cout<
  ;
}

2. 코드 를 일치 시 키 고 처 리 된 패턴 문자열 을 대기 문자열 과 일치 시 키 는 것 은 기본적으로 예비 처리 코드 의 사고 와 일치 하 며 디 테 일 은 약간 차이 가 있 습 니 다.

int kmp(int n,int m)
{int i,j,ret=0;
for(i=1,j=0;i<=m;i++)//  j 0   ,                  ,       
 {while(j>=0&&s1[j+1]!=s2[i])//     ,     
   {j=p[j];
    }
  j++;//      ++
  if(j==n)//    ,    ,j      
  {ret++;
   j=p[j];
  }
 }
 return ret;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

pandas 로 데이터 세트 를 나 누 어 훈련 집합 과 테스트 집합 을 실현 합 니 다.

원리:데이터 세트 를 n 개의 교차 하지 않 는 부분 집합 으로 나 누고 매번 그 중 하 나 를 테스트 집합 으로 선택 하고 나머지 n-1 개의 부분 집합 을 훈련 집 그룹 데이터 매개 변수 설명:...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

9.11 ~ 9.16 훈련 집 --- 비교적 중요, kmp 편

좋은 웹페이지 즐겨찾기