จำนวนรอบหมุนต่ำสุดเพื่อให้ได้สตริงเดิมใน C++

ข้อกำหนดโจทย์

กำหนดสตริง เราต้องหาจำนวนรอบหมุนต่ำสุดที่จำเป็นเพื่อให้ได้สตริงเดิม

ตัวอย่าง

ถ้าสตริงอินพุตคือ "bbbbb" แล้วต้องการการหมุนขั้นต่ำ 1 รอบ

อัลกอริทึม

1. เริ่มต้น result = 0
2. สร้างสตริงชั่วคราวเท่ากับสตริงต้นฉบับต่อกับตัวมันเอง
3. หา substring ของสตริงชั่วคราวขนาดเท่าสตริงต้นฉบับ เริ่มจากตัวอักษรที่สอง คือดัชนี 1
4. เพิ่มตัวนับ
5. ตรวจสอบว่า substring กลายเป็นเท่ากับสตริงต้นฉบับหรือไม่ ถ้าใช่ หยุดลูป มิฉะนั้นไปขั้นตอน 2 และทำซ้ำจากดัชนีถัดไป

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
int getRotationCount(string str) {
  string temp = str + str;
  int n = str.length();
  for (int i = 1; i <= n; ++i) {
    string sub = temp.substr(i, str.size());
    if (str == sub) {
      return i;
    }
  }
  return n;
}
int main() {
  string str = "bbbbb";
  cout << "Rotation count = " << getRotationCount(str) << endl;
  return 0;
}

เมื่อคุณคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

Rotation count = 1