Kira bilangan pasangan rentetan yang berbeza dalam satu kedudukan sahaja

Pengenalan

String terdiri daripada aksara alfanumerik, setiap satunya dikaitkan dengan kedudukan yang ditentukan. Kedudukan aksara berkisar antara 0 hingga panjang rentetan. Watak yang berbeza sama sekali dalam satu kedudukan dipanggil watak bersebelahan.

Dalam artikel ini, kami akan membangunkan kod yang mengambil sebagai input tatasusunan rentetan yang berbeza sama sekali pada satu kedudukan. Mari lihat contoh di bawah untuk memahami topik ini dengan lebih baik -

Contoh

Contoh 1 - str - {"abc", "cba", "dbc", "acc"}

Output - 2

Sebagai contoh, dalam contoh di bawah, dua pasangan {"abc", "dbc"} dan {"abc", acc"} boleh dijana. Rentetan ini berbeza hanya dalam satu kedudukan aksara setiap satu.

Dalam artikel ini, kami akan membangunkan kod yang menggunakan pemetaan untuk menyimpan rentetan yang serupa dan corak untuk mendapatkan jumlah pasangan rentetan. Peta C++ menggunakan pasangan nilai kunci untuk menyimpan dan mendapatkan data dengan kerumitan masa yang berterusan.

Tatabahasa

substr()

Kaedah

substr() digunakan untuk mengakses subrentetan dari mula hingga akhir-1 dalam rentetan yang lebih besar. Semua indeks yang hendak diakses hendaklah bersebelahan dan teratur.

Parameter -

st - kedudukan permulaan

akhir - Kedudukan hujung di mana akses subrentetan ditamatkan

Algoritma

• Menerima vektor rentetan, rentetan

• Pada mulanya mengekalkan kaunter untuk menyimpan kiraan jumlah pasangan yang memenuhi syarat.

• Kekalkan dua peta untuk menyimpan rentetan yang sama serta rentetan yang memenuhi corak yang mengekalkan kad bebas. Mari kita andaikan bahawa pemetaan ini ialah m1.

• Kekalkan peta lain untuk menyimpan rentetan yang serupa. Mari kita andaikan bahawa pemetaan ini ialah m2.

• Lakukan lelaran ke atas tatasusunan input.

• Setiap kali jenis rentetan yang serupa diperhatikan, kiraan yang sepadan dalam peta m2 akan dinaikkan

• Subrentetan dicipta dengan menggantikan aksara individu bagi rentetan menggunakan kad bebas

• Setiap kali jenis corak yang serupa diperhatikan, kiraan yang sepadan dalam plot m1 akan dinaikkan

• Hitung jumlah pasangan rentetan yang diperhatikan dalam m1 dan m2 masing-masing.

• Gunakan nilai jumlah ini untuk meningkatkan kiraan.

Contoh

Coretan kod C++ berikut digunakan untuk mengambil tatasusunan rentetan sebagai input dan mengira jumlah bilangan pasangan yang berbeza dalam satu kedudukan sahaja -

//including the required libraries
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of same pairs
int countPairs(map<string, int> &d) {
   //maintaining the count 
   int sum = 0;
   for (auto i : d)
       sum += (i.second * (i.second - 1)) / 2;
 
   return sum;
}
//called method to calculate strings differing by one character
void chardiff(vector<string> &array, int len , int n ) {
   //count to store pairs
    int cnt = 0;
   //storing strings with wildcard characters
    map<string, int> pattern;
   //storing equivalent strings
    map<string, int> similar;
   //iterating over the array
   for (auto str : array) {
      //if two strings are same , increment the count
       similar[str]+= 1;
 
      // Iterating on a single string
       for (int i = 0; i < len ; i++) {
      // Adding special symbol to the string
       string first = str.substr(0, i);
       string second = str.substr(i + 1);
       string temp =  first + "//" + second ;
 
      //incrementing if similar pattern 
        pattern[temp]+=1;
      }
   }
 
   // Return counted pairs - equal pairs
   int chnged = countPairs(pattern);
   int sim = countPairs(similar);
   cnt =  chnged - sim * len;
   cout << "The count of pairs satisfying the condition are : " << cnt; 
}
 
//calling the main method
int main() {
   int n = 4, len = 3;
   //getting a vector of strings to process
   vector<string> strings = {"get","set","bet","bat"};
   cout << "Vector of strings : " << "\n" ;
   for(auto s : strings){
       cout << s <<"\n";
   }
   //one character different
   chardiff(strings, len , n );
 
   return 0;
}

Output

Vector of strings − 
get
set
bet
bat
The count of pairs satisfying the condition are − 4

Kesimpulan

Peta mensimulasikan proses pemasukan dan kemas kini rekod dengan kerumitan masa O(1). Kaedah subrentetan dalam C++ boleh digunakan untuk mengakses aksara rentetan mengikut susunan antara indeks yang ditentukan. Hasil darab n dan n-1 dibahagikan dengan 2 memberikan hasil tambah sebarang bilangan pasangan.

Atas ialah kandungan terperinci Kira bilangan pasangan rentetan yang berbeza dalam satu kedudukan sahaja. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!