Prefix Matching ( DSA Interview Preparation Problems and Solutions ) ~ Multiplex Coder

Prefix Matching

Problem Description

We have a list of lexicographically sorted strings A. We also have a string B. We need the first and last indexes of strings from A which are having their prefix as B. A can contain duplicate strings.

Return [-1, -1] if no such prefix exists.

Problem Constraints

1 <= |A| <= 105

1 <= ∑|A[i]| <= 106

1 <= |B| <= 105

Input Format

The first line contains an array of strings A.

The second line contains the required prefix B.

Output Format

Return a vector containing first and last indexes and [-1, -1] in case no such prefix exists. Consider 0-based indexing.

Example Input

Input 1:

  A = [a, aa, aab, b, bb, bba, bbb]
 B = bb

Input 2:

 A = [a, b]
 B = c

Example Output

Output 1:

 [4, 6]

Output 2:

 [-1, -1]

Example Explanation

Explanation 1:

 bb occurs as prefix in bb,bba and bb.

Explanation 2:

 c is not present as prefix.

Code:


int n;
string s;
int x[500005][28], nt = 1, id; 
void build(string s){
    int i = 0, v = 0;
    while(i < s.size()){
        if(x[v][s[i]-'a'] == -1)
            v = x[v][s[i++]-'a'] = nt ++;
        else
            v = x[v][s[i++]-'a'];
    }
    if(x[v][26]==-1)
        x[v][26]=id;
    else
        x[v][26]=min(x[v][26],id);
    x[v][27]=max(x[v][27],id);
}
int query(string s){
    int i = 0, v = 0;
    while(i < s.size()){
        if(x[v][s[i]-'a'] == -1){
            v=-1;
            break;
        }
        else
            v = x[v][s[i++]-'a'];
    }
    return v;
}
int left(int v)
{
    int ans;
    while(v!=-1)
    {
        if(x[v][26]!=-1)
        {
            ans=x[v][26];
            break;
        }
        int f=0;
        for(int i=0;i<26;i++)
        {
            if(x[v][i]!=-1)
            {
                v=x[v][i];
                f=1;
                break;
            }
        }
        if(!f)
            v=-1;
    }
    return ans;
}
int right(int v)
{
    int ans;
    while(v!=-1)
    {
        if(x[v][27]!=-1)
            ans=x[v][27];
        int f=0;
        for(int i=25;i>=0;i--)
        {
            if(x[v][i]!=-1)
            {
                v=x[v][i];
                f=1;
                break;
            }
        }
        if(!f)
            v=-1;
    }
    return ans;
}
vector<int> Solution::solve(vector<string> &A, string B) {
    memset(x,-1,sizeof(x));
    nt=1;
    n=A.size();
    for(int i=0;i<n;i++)
    {
        id=i;
        s=A[i];
        build(s);
    }
    s=B;
    int v=query(s);
    vector<int>ans;
    if(v==-1)
    {
        ans.push_back(-1);
        ans.push_back(-1);
    }
    else
    {
        ans.push_back(left(v));
        ans.push_back(right(v));
    }
    return ans;
}

Prefix Matching ( DSA Interview Preparation Problems and Solutions )

Related Post