KMP (단일 모드 일치)
1714 단어 알고리즘
① 단일 문자열 이 일치 하고 일치 하 는 주 소 를 되 돌려 주 며 일치 하 는 총 횟수 를 구한다.
② 순환 원, t = len - next [len]
간단 한 소감:
① next [] 배열 의 유효 범 위 는 [0, len], len 일 때 next [] 가 유효 치 이다.
② next [0] = - 1, next [1] = 0 만 기억 하면 next [] 를 구 하 는 함 수 를 쓸 수 있다.
③ 매 칭 과정 은 O (N) 만 필요 하기 때문에 i 의 값 은 회귀 할 필요 가 없다.여 기 는 오래 고민 되 었 습 니 다. match () 함수 ① 곳 에서 j 의 값 만 바 꾸 면 됩 니 다.
KMP 템 플 릿:
//KMP
/*
next[] ：
next[i]==next[j], next[i+1]
next[i]==next[j], b[0,j-1]==b[i-j,i-1]。
：b[j]==b[i]， next[i+1]=next[i]+1；
：b[j]!=b[i], j=next[j] ， b[j]==b[i]， next[i+1]=next[j]+1;
b[j]==b[i]， j -1， next[i+1]=0;
*/
void getNext(char *s, int *next)
{
int i, j;
int len = strlen(s);
next[0] = -1;
for(i = 0, j = -1; i < len; ++ i)//② j -1，j i
{
if(j == -1 || s[i] == s[j])
{
i ++;
j ++;
next[i] = j;
}
else
j = next[j];
}
}
/*
： b[]="aaaab";
next[]={-1,0,1,2,3}
， ， ， ， b[i+1]==b[j+1]， next[i+1]=next[j+1]， 。
new_next[]={-1,-1,-1,-1,3}
*/
// next[]
void getNext(char *s, int *next)
{
int i, j;
int len = strlen(s);
next[0] = -1;
for(i = 0, j = -1; i < len; ++ i)//② j -1，j i
{
if(j == -1 || s[i] == s[j])
{
i ++;
j ++;
if(s[i] == s[j])
next[i] = next[j];
else
next[i] = j;
}
else
j = next[j];
}
}
void match(char *s, char *ss)// ss s
{
int len1 = strlen(s);
int len2 = strlen(ss);
int i, j;
for(i = 0, j = 0; i < len2;)
{
if(j == -1 || ss[i] == s[j])
{
i ++;
j ++;
if(j == len1)
find = 1;//
}
else//①，i
j = next[j];
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
