fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. // Knuth-Morris-Pratt Algorithm
  8. // bush의 앞에서부터 needle의 최초 위치를 찾아 반환합니다.
  9. size_t kmp(const string& bush, const string& needle)
  10. {
  11.     const size_t needleLen = needle.length();
  12.     const size_t bushLen = bush.length();
  13.  
  14.     // string::find는 패턴 문자열이 비어있을 경우 0을 반환함.
  15.     if (needleLen == 0)
  16.     {
  17.         return 0;
  18.     }
  19.  
  20.  
  21.     // pi[match] == needle[:match+1]의 최대 동일 접두접미사 길이
  22.     vector<size_t> pi(needleLen, 0ul);
  23.  
  24.     for (size_t i = 1, match = 0; i < needleLen; ++i)
  25.     {
  26.         while (match > 0 && needle[i] != needle[match])
  27.             match = pi[match - 1];
  28.         if (needle[i] == needle[match])
  29.             pi[i] = ++match;
  30.     }
  31.  
  32.  
  33.     for (size_t i = 0, match = 0; i < bushLen; ++i)
  34.     {
  35.         // 매치 실패시
  36.         // 성공할 때까지 혹은 더 이상 할 수 없을 때까지 건너뛰기 시도.
  37.         while (match > 0 && bush[i] != needle[match])
  38.         {
  39.             match = pi[match - 1];
  40.         }
  41.  
  42.         // 매치 성공시
  43.         // 다음 문자 검색 준비.
  44.         // 다음 문자가 없다면 검색이 완료된 것이므로 위치 계산 후 반환.
  45.         if (bush[i] == needle[match])
  46.         {
  47.             ++match;
  48.             if (match >= needleLen)
  49.             {
  50.                 // i를 반환하지 않고 이러는 이유는
  51.                 // 현재 i가 검색된 문자열의 뒤를 가리키고 있기 때문임.
  52.                 return i - (match - 1);
  53.             }
  54.         }
  55.     }
  56.  
  57.  
  58.     // 찾을 수 없음.
  59.     return string::npos;
  60. }
  61.  
  62. int main()
  63. {
  64.     string bush;
  65.     string needle;
  66.  
  67.     getline(cin, bush);
  68.     getline(cin, needle);
  69.  
  70.     size_t index = kmp(bush, needle);
  71.     size_t answer = bush.find(needle);
  72.  
  73.     // 구현 검증
  74.     if (answer != index)
  75.     {
  76.         cout << "FAIL! Answer : " << answer << ", Me : " << index << endl;
  77.         return -1;
  78.     }
  79.  
  80.     if (index == string::npos)
  81.     {
  82.         cout << "Couldn't find!" << endl;
  83.     }
  84.     else
  85.     {
  86.         cout << "Index : " << index << endl;
  87.     }
  88.  
  89.     return 0;
  90. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
abaababababcacab
ababc
stdout
copy 
Index : 7
https://ideone.com/dKi0sA
language:
C++14 (clang 8.0)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!