Click here to Skip to main content
15,893,508 members
Please Sign up or sign in to vote.
1.00/5 (3 votes)
See more:
Hello,

Please if I am given a sequence of words S, and a sequence of words T. How do I find the shortest continuous subsequence of words in S such that the words in T appear in that order (in c#)
Thank you.

My current source code is:

C#
public  bool ContainsSubequence<t>(this IEnumerable<t>parent, IEnumerable<t>target)
   {
       bool foundOneMatch = false;
       var enumeratedTarget = target.ToList();
       int enumPos = 0;

       using (IEnumerator<t>parentEnum = parent.GetEnumerator())
       {
           while (parentEnum.MoveNext())
           {
               if (enumeratedTarget[enumPos].Equals(parentEnum.Current))
               {
                   // Match, so move the target enum forward
                   foundOneMatch = true;
                   if (enumPos == enumeratedTarget.Count - 1)
                   {
                       // We went through the entire target, so we have a match
                       return true;
                   }

                   enumPos++;
               }
               else if (foundOneMatch)
               {
                   foundOneMatch = false;
                   enumPos = 0;

                   if (enumeratedTarget[enumPos].Equals(parentEnum.Current))
                   {
                       foundOneMatch = true;
                       enumPos++;
                   }
               }
           }

           return false;
       }
   }


but its not working
Posted
Updated 22-Jun-15 16:16pm
v3
Comments
PIEBALDconsult 19-Jun-15 12:24pm    
Sounds like homework. Try it yourself.

I suppose a rather 'brute force' approach would succeed here.
That is find the first occurrence of the first T item ("find") in S, then find the first occurrence of the second T item ("them") in the following words and so on, until last T item is found. Mark it as 'best current soution'. Continue such a process, updating 'best current solution' appropriately. Eventually the 'best current solution' (possibly empty) is your result.
 
Share this answer
 
Comments
PIEBALDconsult 22-Jun-15 22:13pm    
I'd use a Stack. :D
We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

Try it yourself, you may find it is not as difficult as you think!

If you meet a specific problem, then please ask about that and we will do our best to help. But we aren't going to do it all for you!
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900