- Forum
- General C++ Programming
- Sequence of numbers, periods, repeating
Sequence of numbers, periods, repeating subsequences...
Hi. I need to write a program that checks if a sequence of numbers entered by the user is periodic(by saying periodic I mean that the whole sequence consists only of a repeating period whose members have fixed positions in it). If the sequence is periodic then the program should output the period on the screen, but if it is not (the hardest part) the program has to check which subsequence(again whose members have fixed positions in it) is repeated more often and output that subsequence on the screen. The worst thing is that there can be other numbers between the repeating subsequences. Hope someone can help me preferably with the technical side, not only with the algorithm because I'm a beginner.
Thank you very much in advance.
Thank you very much in advance.
Please define [repeating period] and [fixed positions].
Can you do it with an actual sequence of numbers as an example, and illustrate these various components.
Can you do it with an actual sequence of numbers as an example, and illustrate these various components.
Sure. For example we have this sequence - 4265426542654265 . In this sequence 4265 is the period.
and in this example - 214573945733314578 - 457 is the most repeating subsequence.
and in this example - 214573945733314578 - 457 is the most repeating subsequence.
There's a big difference in my answer depending on whether this is "algorithms" or "CS101". Right now I'm leaning toward the latter, but if you are studying the former the answer will be much more complex.
[edit] Don't assume I'm being a jerk. All questions I ask are calculated to help you best.
[edit] Don't assume I'm being a jerk. All questions I ask are calculated to help you best.
Last edited on
Thanks for your reply and interest in my topic. There is no difference for me in which way or using what the solution is given. You will help me a lot with any useful answer. Thank you.
Fine. Finding the period is exceedingly simple.
Given abCabCabCab
Can you find a copy of half the input in the input not at index zero? (Yes, abCabCabCab.)
Is the remainder of the string repetitions of the potential period?
All this can be easily done with the simple std::string class, using find() and substr() and a little concatenation.
Finding the "most frequently occurring substring" is a common CS problem. You can brute-force it, much like finding the most frequently occurring character in a string, but for full algorithms credit you should use a suffix array or suffix tree (C++ provides you with both the std::vector and std::map classes to help here).
Keep in mind that there may be more than one answer for this one -- you'll need to keep a list of results.
Good luck!
Given abCabCabCab
Can you find a copy of half the input in the input not at index zero? (Yes, abCabCabCab.)
Is the remainder of the string repetitions of the potential period?
All this can be easily done with the simple std::string class, using find() and substr() and a little concatenation.
Finding the "most frequently occurring substring" is a common CS problem. You can brute-force it, much like finding the most frequently occurring character in a string, but for full algorithms credit you should use a suffix array or suffix tree (C++ provides you with both the std::vector and std::map classes to help here).
Keep in mind that there may be more than one answer for this one -- you'll need to keep a list of results.
Good luck!
Syok,
Did you resolve your problem? I am writing a matlab project that uses your same algorithm and am pretty stuck. Can you send me your code for extracting a periodic subsequence? Thank you!
Did you resolve your problem? I am writing a matlab project that uses your same algorithm and am pretty stuck. Can you send me your code for extracting a periodic subsequence? Thank you!
Asking other people to do your homework, hmm?
Why not just read the solution two posts above yours?
Why not just read the solution two posts above yours?
You're an idiot. Do not assume I am asking for a HW solution. My
problem is more difficult, extracting an internal period from a non-
terminating (but possibly periodic) sequence which could have an initial
transient at its beginning. I would hope that I could integrate some
of Syok's solution techniques in my problem...
problem is more difficult, extracting an internal period from a non-
terminating (but possibly periodic) sequence which could have an initial
transient at its beginning. I would hope that I could integrate some
of Syok's solution techniques in my problem...
Hey Syok,
I wonder if you are still subscribing to this forum. If you have time, I'd like to see how you approached/solved your periodicity problem. Thanks!
I wonder if you are still subscribing to this forum. If you have time, I'd like to see how you approached/solved your periodicity problem. Thanks!
Topic archived. No new replies allowed.