check is string은 다른 문자열의 부분 문자열입니다.

Question

substr 함수를 사용하지 않고 문자열이 C에서 다른 문자열의 부분 문자열인지 어떻게 확인합니까?

Answer 1

사용하지 마십시오 substr ... 사용 strstr/strnstr!

진지하게, 정확히 똑같은 것을하지 않으면 다른 어떤 것도 빠르지 않을 것입니다. 왜 그걸 원하지 않는거야?

편집 : 그래, 더 나은 점근 성능이있는 알고리즘이 있습니다. 단일 문자열에 대한 텍스트 검색의 경우 표준 라이브러리보다 성능이 뛰어나다는 사실을 알고 놀랐습니다.

Answer 2

롤링 해시 방법 (Rabin-Karp)을 사용하거나 KMP을 구현할 수 있습니다. 이는 상태 시스템과 비슷합니다.

일반적으로 Rabin-Karp는 여러 대상 문자열을 검색 할 때 사용됩니다. 해시 평등이 아닌 실제 평등을 위해 필요한 두 번째 검사는 원본 문자열을 한 번만 검사 할만큼 가치가 있기 때문에 일반적으로 사용됩니다 . 당신의 경우에, 어느 쪽이든은 잘 할 것이다.

또한 O (n^2) 인보다 간단한 솔루션이 있으며 원본 문자열의 모든 위치에서 대상 문자열을 확인해야합니다.

Answer 3

void main() 
{ 
    char str[80],search[10]; 
    int count1=0,count2=0,i,j,flag; 




    puts("Enter a string:"); 
    gets(str); 

    puts("Enter search substring:"); 
    gets(search); 

    //determines the src length 
    while (str[count1]!='\0') 
     count1++; 
    //determines the key length 
    while (search[count2]!='\0') 
     count2++; 

    for(i=0;i<=count1-count2;i++) 
    { 
     for(j=i;j<i+count2;j++) 
     { 
      flag=1; 
      if (str[j]!=search[j-i]) 
      { 
       flag=0; 
       break; 
      } 
     } 
     if (flag==1) 
      break; 
    } 
    if (flag==1) 
     puts("SEARCH SUCCESSFUL!"); 
    else 
     puts("SEARCH UNSUCCESSFUL!"); 
    getch(); 
}