z-algorithm

[shsh111]

i hope someone here can help me with this quistion...
Finding Tandem Repeats: Suppose that we want to find all short tied repeats w within a string A = xwwy, |w| < 8. This type of repeat is called a tandem repeat and it occurs very often in biological sequences. Propose an algorithm, evaluate its efficiency, and write code.
thanks :)

[JamesCherrill]

DaniWeb Member Rules include:
"Do provide evidence of having done some work yourself if posting questions from school or work assignments"
http://www.daniweb.com/community/rules

Have you tried Google or Bing?

[ChrisHunter]

You could put each charactor of the string into separate inidex's of an array. Then you could loop through the array, storing the current and the previous array index value in separate variables to compare.

It's hard to explain and probably not the best way to do it but this is how i would do it in C# you should be able to do the same in Java quite easily (i'm not too good at Java):

        static void Main(string[] args)
        {
            // Asks for input from user
            Console.WriteLine("Please enter a sting");
            // Reads, stores and duplicates input
            char[] copy1 = Console.ReadLine().ToCharArray();
            char[] copy2 = copy1;

            // Loops through for each array index (each charactor of the input
            for (int i = 0; i < copy1.Length; i++)
            {
                // Check that arrayin length is not exceeded if 1 is added to the value of i when access array index of copy 2
                if ((i + 1) < copy1.Length)
                {
                    // The increment is done at index
                    if (copy1[i] == copy2[i + 1])
                    {
                        Console.WriteLine("The two charactors were the same");
                        Console.ReadLine();
                        break;
                    }
                }
                else
                {
                    Console.WriteLine("There were not charactor duplicates in the string entered");
                    Console.ReadLine();
                    break;
                }
            }
        }

Hope this helps, let me know if you have any problems with it.

[Taywin]

I believe this is a homework question and it is not "clear" to me for certain parts. When it said "find," does it mean to simply display all the repeat or store all of their indexes? Anyway, if you want an algorithm, the best you could do is O(n+m) where n is the length of the string to be checked and m is the lenght of the substring. Check Rabin Karp algorithm for this. I think it is the easiest to implement.

[SagarSe7en]

ChrisHunter has given a good example! I believe writing it in java will not be difficult.

Use the code given by ChrisHunter.

PS:

DaniWeb Rules:

Do Not Send PM asking for help.

Start a Thread and immediate attention will be given by other moderators and posters.

Click Here