จำนวนสตริงย่อยที่มีอักขระ X อย่างน้อยหนึ่งครั้งใน C++

เราได้รับสตริง str[] และอักขระ X เป้าหมายคือการค้นหาสตริงย่อยของ str[] เพื่อให้สตริงย่อยทั้งหมดมี X อย่างน้อยหนึ่งครั้ง สำหรับ str[]=”abc '' และ X='a' สตริงย่อยที่มี 'a' อย่างน้อยหนึ่งครั้งคือ “a”, “ab”, “abc” นับเป็น 3

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − str[] =“aabccd” X=’c’

ผลผลิต − จำนวนสตริงย่อยที่มีอักขระ X อย่างน้อยหนึ่งครั้งคือ − 14

คำอธิบาย − สตริงย่อยที่มีอย่างน้อยหนึ่ง 'c' จะเป็น :“c”, “c”, “bc”, “cc”, “cd”, “abc”, “bcc”, “ccd”, “aabc”, “ aabcc”, “bccd”, “aabcc”, “abccd”, “aabccd”

ป้อนข้อมูล − str[] =“การตั้งค่า” X=’s’

ผลผลิต − จำนวนสตริงย่อยที่มีอักขระ X อย่างน้อยหนึ่งครั้งคือ − 14

คำอธิบาย − สตริงย่อยมีอย่างน้อยหนึ่ง 's' คือ:“s”, “s”, “se”, “gs”, “set”, “ngs”, “sett”, “ings”, “setti”, “ tings”, “settin”, “ttings”, “setting”, “ettings”, “settings”

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

ในแนวทางนี้ เราทราบดีว่าจำนวนสตริงย่อยทั้งหมดของสตริงที่มีอักขระ n ตัวคือ n*(n+1)/2.

ตอนนี้เราจะสำรวจสตริงและนับอักขระก่อนอักขระ X เป็นแบบชั่วคราว ทันทีที่พบ X สตริงที่มี X จะมีความยาว temp+1 ตอนนี้เรามีสตริงย่อยจำนวน X ที่มี X จะเป็นอักขระที่เหลือ (ดัชนีความยาวปัจจุบัน) X ( temp+1) เพิ่มสิ่งนี้เพื่อนับ ตอนนี้อัปเดต temp=0 และดำเนินการ X ถัดไปจนถึงจุดสิ้นสุดของสตริง ในตอนท้ายเราได้นับเป็นจำนวนสตริงย่อยที่มีอักขระ X อย่างน้อยหนึ่งครั้ง

• ใช้สตริงสตริงและอักขระ x

• ฟังก์ชัน sub_x(char str[],int length,char x) รับสตริง มันคือความยาว อักขระ x และคืนค่าจำนวนสตริงย่อยที่มีอักขระ x อย่างน้อยหนึ่งครั้ง

• นับเริ่มต้นเป็น 0 ใช้ temp เป็นอักขระก่อน x ตัวแรกใน str[] เป็น 0 ในตอนแรก

• ใช้ขนาดการนับเริ่มต้น*(size+)/2 สำหรับจำนวนสตริงย่อยที่เป็นไปได้ทั้งหมดของ str[]

• Traverse str[] ใช้ for loop จาก i=0 ถึง i

• ถ้า str[i] ไม่ใช่ x ให้เพิ่ม temp เป็นอักขระก่อน x ตัวแรก

• ถ้า str[i] ==x ความยาวของสตริงรวม x จะเป็น temp+1 อักขระที่เหลือของ str[] จะมีความยาว-i

• สตริงย่อยทั้งหมดจะเป็น ( temp+1) * (length-i) เพิ่มสิ่งนี้เพื่อนับ ตอนนี้ให้อัปเดต temp=0 สำหรับการทำซ้ำครั้งต่อไป

• ทำเช่นนี้จนกว่าจะถึงจุดสิ้นสุดของ str[]

• ผลตอบแทนนับเป็นผลลัพธ์ในตอนท้าย

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int sub_x(string str, int length, char x){
   int count = 0;
   int temp = 0;
   for (int i = 0; i < length; i++){
      if (str[i] == x){
         int temp_2 = temp + 1;
         count = count + temp_2 * (length - i);
         temp = 0;
      }
      else{
         temp++;
      }
   }
   return count;
}
int main(){
   string str = "abcabbc";
   int length = str.length();
   char x = 'a';
   cout<<"Count of sub-strings that contain character X at least once are: "<<sub_x(str, length,
x);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of sub-strings that contain character X at least once are: 19