Careercup

2014-05-12 06:12

原题：

Write a function to retrieve the number of a occurrences of a substring(even the reverse of a substring) in a string without using the java substring() method. 

Ex: 'dc' in 'abcd' occurs 2 times (dc, cd).

题目：写一个函数来统计模式串在文本中出现的次数，不过这次模式的反转也算数。比如“abcd”中dc算出现两次。

解法：按照这种算法，应该是原模式串匹配一次，反转模式串再匹配一次，然后结果加起来乘以二。如果模式串本身是回文串的话，那就只匹配一次。匹配使用KMP算法。

代码：

  1 // http://www.careercup.com/question?id=5188169901277184
  2 #include <iostream>
  3 #include <string>
  4 #include <vector>
  5 using namespace std;
  6 
  7 class Solution {
  8 public:
  9     int countWord(const string &word, string &pattern) {
 10         lw = (int)word.length();
 11         lp = (int)pattern.length();
 12         
 13         if (lw == 0 || lp == 0) {
 14             return 0;
 15         }
 16         
 17         if (lw < lp) {
 18             return 0;
 19         }
 20         
 21         int result = 0;
 22         if (isPalindrome(pattern)) {
 23             calculateNext(pattern);
 24             result += KMPMatch(word, pattern);
 25         } else {
 26             calculateNext(pattern);
 27             result += KMPMatch(word, pattern);
 28             reverse(pattern.begin(), pattern.end());
 29             calculateNext(pattern);
 30             result += KMPMatch(word, pattern);
 31             reverse(pattern.begin(), pattern.end());
 32             result *= 2;
 33         }
 34         next.clear();
 35         
 36         return result;
 37     }
 38 private:
 39     int lw;
 40     int lp;
 41     vector<int> next;
 42     
 43     bool isPalindrome(const string &s) {
 44         int len = (int)s.length();
 45         int i;
 46 
 47         if (len <= 1) {
 48             return true;
 49         }
 50 
 51         for (i = 0; i < len - 1 - i; ++i) {
 52             if (s[i] != s[len - 1 - i]) {
 53                 return false;
 54             }
 55         }
 56 
 57         return true;
 58     }
 59 
 60     void calculateNext(const string &pattern) {
 61         int i = 0;
 62         int j = -1;
 63         
 64         next.resize(lp + 1);
 65         next[0] = -1;
 66         while (i < lp) {
 67             if (j == -1 || pattern[i] == pattern[j]) {
 68                 ++i;
 69                 ++j;
 70                 next[i] = j;
 71             } else {
 72                 j = next[j];
 73             }
 74         }
 75     }
 76     
 77     int KMPMatch(const string &word, const string &pattern)
 78     {
 79         int index;
 80         int pos;
 81         int result;
 82         
 83         index = pos = 0;
 84         result = 0;
 85         while (index < lw) {
 86             if (pos == -1 || word[index] == pattern[pos]) {
 87                 ++index;
 88                 ++pos;
 89             } else {
 90                 pos = next[pos];
 91             }
 92             
 93             if (pos == lp) {
 94                 pos = 0;
 95                 ++result;
 96             }
 97         }
 98         
 99         return result;
100     }
101 };
102 
103 int main()
104 {
105     string word, pattern;
106     Solution sol;
107     
108     while (cin >> word >> pattern) {
109         cout << sol.countWord(word, pattern) << endl;
110     }
111     
112     return 0;
113 }