Best algorithm to find a repeating pattern

Question 1

What are the best algorithms available to find longest repeating patterns of characters in a string using .net?

Question 2

You will have to be more specific. Maybe give some examples. Also, have you done any research yourself already? If so, tell us what you found.

Question 3

you can build a dictionary, like what lossless data compression algorithms do. See for exampleen.wikipedia.org/wiki/Dictionary_coder

Question 4

your 'edit' does not make it any less vague, IMO.Try to do what Space_C0wb0y suggest.

Question 5

I'm unsure why you want thelongest pattern. Clearly for the string "abcabca" the pattern "abc" is more interesting than "abcabc"

Question 6

I guess that you speak aboutpattern discovery. Take a look at some elementary aproach (source)

private static Dictionary<string, int> FindPatterns(string value) {  List<string> patternToSearchList = new List<string>();  for (int i = 0; i < value.Length; i++) {    for (int j = 2; j <= value.Length / 2; j++) {      if (i + j <= value.Length) {        patternToSearchList.Add(value.Substring(i, j));      }    }  }  // pattern matching  Dictionary<string, int> results = new Dictionary<string, int>();  foreach (string pattern in patternToSearchList) {    int occurence = Regex.Matches(value, pattern, RegexOptions.IgnoreCase).Count;    if (occurence > 1) {      results[pattern] = occurence;    }  }  return results;}static void Main(string[] args) {  Dictionary<string, int> result = FindPatterns("asdxgkeopgkajdflkjbpoijadadafhjkafikeoadkjhadfkjhocihakeo");  foreach (KeyValuePair<string, int> res in result.OrderByDescending(r => r.Value)) {    Console.WriteLine("Pattern:" + res.Key + " occurence:" + res.Value.ToString());  }  Console.Read();}

The algorithm consist of 2 stages.

Choose pattern
Find pattern in input string (Algorithm ofpattern matching)

It is used Regex for pattern matching. There are other more advanced algorithms. These algorithms are enlisted on addresshttp://www-igm.univ-mlv.fr/~lecroq/string/However, code samples are written in C. Also you'd take a look onBoyer-Moore algorithm for pattern matching, written in C#

Question 7

I thinks this is kind of brute force method. Are there algorithms to do this using dynamic programming or some other method ?

Question 8

Yes, it's brute force method. I expanded my answer.

Question 9

Pseudocode:

For N=1 to InputString.Length-1  rotatedString = RotateStringByN(InputString,N)  For N=0 to InputString.Length-1     StringResult[N] = if (rotatedString[N]==InputString[N]) then                            InputString[N]                         else                             Convert.ToChar(0x0).ToString()  RepeatedStrings[] = String.Split(StringResult, Convert.ToChar(0x0).ToString())  SaveLongestStringFrom(RepeatedStrings)

... Or just look here atSO thread for other solutions.

Oleg Svechkarenko 2,51625 silver badges31 bronze badges · Accepted Answer · 2011-03-28 13:44:46Z

I guess that you speak aboutpattern discovery. Take a look at some elementary aproach (source)

private static Dictionary<string, int> FindPatterns(string value) {  List<string> patternToSearchList = new List<string>();  for (int i = 0; i < value.Length; i++) {    for (int j = 2; j <= value.Length / 2; j++) {      if (i + j <= value.Length) {        patternToSearchList.Add(value.Substring(i, j));      }    }  }  // pattern matching  Dictionary<string, int> results = new Dictionary<string, int>();  foreach (string pattern in patternToSearchList) {    int occurence = Regex.Matches(value, pattern, RegexOptions.IgnoreCase).Count;    if (occurence > 1) {      results[pattern] = occurence;    }  }  return results;}static void Main(string[] args) {  Dictionary<string, int> result = FindPatterns("asdxgkeopgkajdflkjbpoijadadafhjkafikeoadkjhadfkjhocihakeo");  foreach (KeyValuePair<string, int> res in result.OrderByDescending(r => r.Value)) {    Console.WriteLine("Pattern:" + res.Key + " occurence:" + res.Value.ToString());  }  Console.Read();}

The algorithm consist of 2 stages.

Choose pattern
Find pattern in input string (Algorithm ofpattern matching)

It is used Regex for pattern matching. There are other more advanced algorithms. These algorithms are enlisted on addresshttp://www-igm.univ-mlv.fr/~lecroq/string/However, code samples are written in C. Also you'd take a look onBoyer-Moore algorithm for pattern matching, written in C#

I thinks this is kind of brute force method. Are there algorithms to do this using dynamic programming or some other method ?

Movatterモバイル変換

Collectives™ on Stack Overflow

Best algorithm to find a repeating pattern

2 Answers2

2 Comments

Comments

Your Answer

Sign up orlog in

Post as a guest

Linked

Related

Hot Network Questions

Subscribe to RSS