Skip to content
Related Articles

Related Articles

Maximum length prefix of one string that occurs as subsequence in another

View Discussion
Improve Article
Save Article
  • Difficulty Level : Easy
  • Last Updated : 13 Jul, 2022
View Discussion
Improve Article
Save Article

Given two strings s and t. The task is to find maximum length of some prefix of the string S which occur in string t as subsequence.

Examples : 

Input : s = "digger"
        t = "biggerdiagram"
Output : 3
digger
biggerdiagram
Prefix "dig" of s is longest subsequence in t.

Input : s = "geeksforgeeks"
        t = "agbcedfeitk"
Output : 4

A simple solutions is to consider all prefixes on by one and check if current prefix of s[] is a subsequence of t[] or not. Finally return length of the largest prefix.

An efficient solution is based on the fact that to find a prefix of length n, we must first find the prefix of length n – 1 and then look for s[n-1] in t. Similarly, to find a prefix of length n – 1, we must first find the prefix of length n – 2 and then look for s[n – 2] and so on. 
Thus, we keep a counter which stores the current length of prefix found. We initialize it with 0 and begin with the first letter of s and keep iterating over t to find the occurrence of the first letter. As soon as we encounter the first letter of s we update the counter and look for second letter. We keep updating the counter and looking for next letter, until either the string s is found or there are no more letters in t.

Below is the implementation of this approach: 

C++




// C++ program to find maximum 
// length prefix of one string 
// occur as subsequence in another
// string.
#include<bits/stdc++.h>
using namespace std;
  
// Return the maximum length 
// prefix which is subsequence.
int maxPrefix(char s[], char t[])
{
    int count = 0;
  
    // Iterating string T.
    for (int i = 0; i < strlen(t); i++)
    {
        // If end of string S.
        if (count == strlen(s))
            break;
  
        // If character match, 
        // increment counter.
        if (t[i] == s[count])
            count++;
    }
  
    return count;
}
  
// Driven Code
int main()
{
    char S[] = "digger";
    char T[] = "biggerdiagram";
  
    cout << maxPrefix(S, T) 
         << endl;
  
    return 0;
}

Java




// Java program to find maximum
// length prefix of one string 
// occur as subsequence in another
// string.
public class GFG {     
      
    // Return the maximum length 
    // prefix which is subsequence.
    static int maxPrefix(String s, 
                         String t)
    {
        int count = 0;
      
        // Iterating string T.
        for (int i = 0; i < t.length(); i++)
        {
            // If end of string S.
            if (count == s.length())
                break;
      
            // If character match,  
            // increment counter.
            if (t.charAt(i) == s.charAt(count))
                count++;
        }
      
        return count;
    }
      
    // Driver Code
    public static void main(String args[])
    {
        String S = "digger";
        String T = "biggerdiagram";
      
        System.out.println(maxPrefix(S, T));
    }
}
// This code is contributed by Sumit Ghosh

Python 3




# Python 3 program to find maximum 
# length prefix of one string occur
# as subsequence in another string.
  
  
# Return the maximum length 
# prefix which is subsequence.
def maxPrefix(s, t) :
    count = 0
  
    # Iterating string T.
    for i in range(0,len(t)) :
          
        # If end of string S.
        if (count == len(s)) :
            break
  
        # If character match, 
        # increment counter.
        if (t[i] == s[count]) :
            count = count + 1
              
  
    return count
  
  
# Driver Code
S = "digger"
T = "biggerdiagram"
  
print(maxPrefix(S, T))
  
  
# This code is contributed
# by Nikita Tiwari.

C#




// C# program to find maximum 
// length prefix of one string
// occur as subsequence in 
// another string.
using System;
  
class GFG 
{     
      
    // Return the maximum length prefix 
    // which is subsequence.
    static int maxPrefix(String s, 
                         String t)
    {
        int count = 0;
      
        // Iterating string T.
        for (int i = 0; i < t.Length; i++)
        {
            // If end of string S.
            if (count == s.Length)
                break;
      
            // If character match, 
            // increment counter.
            if (t[i] == s[count])
                count++;
        }
      
        return count;
    }
      
    // Driver Code
    public static void Main()
    {
        String S = "digger";
        String T = "biggerdiagram";
      
        Console.Write(maxPrefix(S, T));
    }
}
  
// This code is contributed by nitin mittal

PHP




<?php
// PHP program to find maximum 
// length prefix of one string 
// occur as subsequence in another
// string.
  
// Return the maximum length 
// prefix which is subsequence.
function maxPrefix($s, $t)
{
    $count = 0;
  
    // Iterating string T.
    for ($i = 0; $i < strlen($t); $i++)
    {
        // If end of string S.
        if ($count == strlen($s))
            break;
  
        // If character match,
        // increment counter.
        if ($t[$i] == $s[$count])
            $count++;
    }
  
    return $count;
}
  
// Driver Code
{
    $S = "digger";
    $T = "biggerdiagram";
  
    echo maxPrefix($S, $T) ;
  
    return 0;
}
  
// This code is contributed by nitin mittal.
?>

Javascript




<script>
  
// JavaScript program to find maximum
// length prefix of one string 
// occur as subsequence in another
// string.
  
    // Return the maximum length 
    // prefix which is subsequence.
    function maxPrefix(s,t)
    {
        let count = 0;
      
        // Iterating string T.
        for (let i = 0; i < t.length; i++)
        {
            // If end of string S.
            if (count == s.length)
                break;
      
            // If character match,  
            // increment counter.
            if (t[i] == s[count])
                count++;
        }
      
        return count;
    }
  
  
// Driver Code
  
    let S = "digger";
    let T = "biggerdiagram";
      
    document.write(maxPrefix(S, T)); 
          
</script>

Output

3

This article is contributed by Anuj Chauhan. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks. 


My Personal Notes arrow_drop_up
Recommended Articles
Page :

Start Your Coding Journey Now!