Ən uzun ümumi uzantı

Bir s sətri və bəzi cütlər (L, R) verildikdə, L və R-dən başlayan ən uzun alt sətrin uzunluğunu çıxaracaq bir funksiya yazın.

misal

INPUT

s = "abcbabcb"

Sorğular: (1,3), (1,5), (0,1)

ÇIXDI

1, (1,3) üçün indeks 1-dən başlayaraq 'b', indeks 3-də də 'b' var, ancaq digər işarələr indeks 3-dən başlayaraq (1,5) üçün 1 ilə uyğun gəlmir "bcb" və indeks 5-də (0) charcters üçün uyğun olmayan "bcb" 0,1 var

Alqoritm

Hər bir LCE sorğusu üçün

1. Uzunluğu 0-a başlayın

2. L və R indekslərindən başlayan simvolları müqayisə etməyə başlayın

3. Simvollar uyğun gəlirsə, bu simvol ən uzun ümumi uzantıdadır, beləliklə uzunluğu artırın

4. Başqa bir şey, əgər simvol uyğun deyilsə, uzunluğu qaytarın

C ++ Proqramı

#include<bits/stdc++.h>
using namespace std;

//function to find LCE
int LCE(string str, int n, int L, int R)
{
    int length = 0;
    //till characters dont match
    while (str[L+length] == str[R+length] &&
            R+length < n)
        length++;

    return(length);
}


int main()
{
    int L = 1;
    int R = 5;
    string str = "abcbabcb";
    int n = str.length();


    cout<<LCE(str, n, L, R);

    return (0);
}

Yoxla

 

Şərh yaz

Translate »