string_matching_1753.cpp (680B)
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 5 struct S { 6 std::string w; 7 std::string t; 8 9 size_t size() const { return w.size() + 1 + t.size(); } 10 11 char operator[](size_t i) const { 12 if (i < w.size()) return w.at(i); 13 if (i > w.size()) return t.at(i-w.size()-1); 14 return '$'; 15 } 16 }; 17 18 int main() { 19 S s; 20 std::cin >> s.t >> s.w; 21 size_t c{0}; 22 std::vector<size_t> z(s.size(), 0); 23 z[0] = s.w.size(); 24 for (size_t i = 1, j = 0, k = 0; i < s.size(); i++) { 25 if (j < i || z[i-k] == j-i) { 26 for (j = std::max(i, j); j < s.size() && s[j] == s[j-i]; j++) ; 27 z[k=i] = j-i; 28 } else z[i] = std::min(z[i-k], j-i); 29 c += z[i] == s.w.size(); 30 } 31 std::cout << c << "\n"; 32 }