Nombre maximal de fois qu’une chaîne donnée doit être concaténée pour former une sous-chaîne d’une autre chaîne

class GFG

{

    

    

    

    static void computeLPSArray(String pat, int M,

                         int []lps)

    {

        

        

        int len = 0;

    

        

        lps[0] = 0;

    

        

        int i = 1;

        while (i < M)

        {

    

            

            

            if (pat.charAt(i) == pat.charAt(len))

            {

                len++;

                lps[i] = len;

                i++;

            }

    

            

            else

            {

                if (len != 0)

                {   

                    len = lps[len - 1];

                }

    

                

                else

                {

                    lps[i] = 0;

                    i++;

                }

            }

        }

    }

    

    

    static int KMPSearch(String pat, String txt)

    {

        int M = pat.length();

        int N = txt.length();

    

        

        

        int lps[] = new int[M];

    

        

        

        computeLPSArray(pat, M, lps);

    

        

        int i = 0;

    

        

        int j = 0;

        while (i < N)

        {   

            if (pat.charAt(j) == txt.charAt(i))

            {

                j++;

                i++;

            }

    

            

            if (j == M)

            {

                return 1;

                

            }

    

            

            else if (i < N

                     && pat.charAt(j) != txt.charAt(i))

            {

    

                

                

                

                if (j != 0)

                    j = lps[j - 1];

                else

                    i = i + 1;

            }

        }

    

        

        return 0;

    }

    

    

    

    

    static void maxRepeating(String seq, String word)

    {

      

        

        int resCount = 0;

    

        

        

        String curWord = word;

    

        

        

        int numWords = seq.length() / word.length();

    

        

        for (int i = 0; i < numWords; i++)

        {

    

            

            if (KMPSearch(curWord, seq) == 1)

            {

    

                

                curWord += word;

    

                

                resCount++;

            }

    

            

            else

                break;

        }

    

        

        System.out.print(resCount);

    }

    

    

    public static void main (String[] args)

    {       

        String S1 = "ababc", S2 = "ab";

    

        

        maxRepeating(S1, S2);

    }

}

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut