Finding Names

Kapil is a number freak. Kapil likes to play with Sets. He is also obsessed with the name Kapil. He likes to calculate the number of times Kapil can be generated from a given text.
From the above paragraph Kapil can be derived 754 times. As we look through the alphabets, it’s easy to find a ‘k’, then find an ‘a’, then ‘p’ and so on. Kapil wants to check whether his calculation is right.

Your task is to write a code that calculate the number of ways a string Name can appear in a string Paragraph modulo 100000001.

 

Input 

The first line of input gives the number of test cases, N(1 ≤ N ≤ 30).
Each test case consists of 2 lines as Input. First line gives the Name; the second line contains the Paragraph.
Each string contains only lower-case letters and spaces.(1 ≤ length of Name, Paragraph ≤ 1000.

 

Output 

For each test case, print the number of times a string Name appears in a string Paragraph modulo 100000001.

 

Sample Input 

3

kapil

kapil is a number freak hence kapil likes to play with sets he is also obsessed with the name kapil he likes to calculate the number of times kapil can be generated from a given text

abc abc

aaaaa bbbbb ccccc

man nam

manning a name

 

Sample Output 

754

0

6

 

using System;

using System.Collections.Generic;

using System.Collections;

using System.Linq;

using System.Text;

 

namespace ConsoleApplication1

{

    class Program

    {

        static void Main(string[] args)

        {

            string name = "man nam";

            string paragraph = "manning a name";

            //Removing other characters from paragraph

            for (int i = 0; i < paragraph.Length; i++)

            {

                if (!name.Contains(paragraph[i]))

                {

                    paragraph = paragraph.Remove(i, 1);

                    i–;

                }

            }

            int found = -1;

            //Initializing start pointer

            int[] startPointer = new int[name.Length];

            for (int i = 0; i < name.Length; i++)

            {

                int flag = 0;

                for (int j = found + 1; j < paragraph.Length; j++)

                {

                    if (name[i] == paragraph[j])

                    {

                        startPointer[i] = j;

                        found = j;

                        flag = 1;

                        break;

                    }

                }

                if (flag == 0)

                {

                    Console.WriteLine("Number of ways = 0");

                    return;

                }

            }

            //Initializing end pointer

            int[] endPointer = new int[name.Length];

            found = paragraph.Length;

            for (int i = name.Length – 1; i >= 0; i–)

            {

                for (int j = found – 1; j >= 0; j–)

                {

                    if (name[i] == paragraph[j])

                    {

                        endPointer[i] = j;

                        found = j;

                        break;

                    }

                }

            }

            int[] pointer = new int[name.Length];

            //Initializing pointer array

            for (int i = 0; i < name.Length; i++)

                pointer[i] = startPointer[i];

            pointer[name.Length – 1]–;

            int p = name.Length – 1;

            int numberOfWays = 0;

            //Calculating number of ways

            do

            {

                p = name.Length – 1;

            label:

                pointer[p]++;

                if (pointer[p] <= endPointer[p])

                {

                    if (paragraph[pointer[p]] != name[p])

                        goto label;

                }

                if (pointer[p] > endPointer[p] && p != 0)

                {

                    pointer[p] = startPointer[p];

                    p–;

                    goto label;

                }

                else if (pointer[p] > endPointer[p] && p == 0)

                {

                    break;

                }

                else

                {

                    int flag = 0;

                    //Checking pointer values

                    for (int i = 0; i < name.Length – 1; i++)

                    {

                        if (pointer[i] >= pointer[i + 1])

                        {

                            flag = 1;

                            break;

                        }

                    }

                    if (flag == 0)

                        numberOfWays++;

                }

            }while(pointer[0] <= endPointer[0]);

            Console.WriteLine("Number of ways = " + numberOfWays);

        }

    }

}

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s