Hướng dẫn giải của String Matching

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: tranxuantruong

  • Bài này có nhiều cách làm, có thể sử dụng các thuật toán hash, kmp, z... mỗi cái đều có cái hay, cái lợi thế và ưu điểm riêng

  • Tự tìm hiểu và code để có thể hiểu rõ cách làm nha, còn dưới đây là một đoạn code đơn giản sử dụng thuật toán z để giải bài tập này:

Code

int main(){
   string s; cin >> s; 
   string t; cin >> t; 

   s=t+'#'+s;
   int n=s.size();
   int x=0;
   int y=0;
   vector <int> z(n);
   for(int i=1; i<n; ++i){
      z[i]=max((int)0, min(z[i-x], y-i+1));

      for( ; i+z[i]<n && s[z[i]]==s[i+z[i]]; ){
         x=i;
         y=i+z[i];
         ++z[i];
      }
   }

   int ans=count(z.begin(), z.end(), t.size());

   cout <<ans <<endl;

   return 0;  
}

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.