How do I find out the repetitive strings?

You want to create a function that checks whether the string is repeated or not.

For example,

[
    '0045662100456621004566210045662100456621', #Repeat '00456621'
    '0072992700729927007299270072992700729927', #Repeat '00729927'
    Repeat '001443001443001443001443001443001443001443', # '001443'
    '037037037037037037037037037037037037037037', # '037' Repeat
    Repeat '047619047619047619047619047619047619', # '047619'
    Repeat '002457002457002457002457002457002457002457002457', # '002457'
    Repeat '001221001221001221001221001221001221', # '001221'
    '001230012300123001230012300123001230012300123', #Repeat '00123'
    '001394700139470013947001394700139470013947001394700139470013947', #Repeat '0013947'
    '001001001001001001001001001001001001001001', #Repeat '001'
    Repeat '001406469760900140646976090014064697609', # '0014064697609'
]

is when the string is repeated over and over.

[
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

is not the case.

A very long string can come in, or a repeating string can be very long. I'm using one, two, three... It's a method of increasing the length of the string that repeats like this It's so slow like this that I want to know if there's any other way.

Whether the entire string is repeating itself If it's repeated, can you tell me which string is the shortest of the repeated strings?

string python pattern-matching

2022-09-22 13:01

1 Answers

I think the simplest way to avoid repetition is as follows

def principal_period(s):
    i = (s+s).find(s, 1, -1)
    return None if i == -1 else s[:i]

The code was created by analyzing patterns between repeated and non-repeated structures. The pattern is as follows:

It can be expressed as S = ABBAB. (However, A and B are also strings)

If A = aA' and B = B'b for any character a and b, S+S = ABABABABAB = aA'BABABAB'b.

Therefore, if S has a repeating structure, (S+S)[1:-1] is A'BABABAB' find(A'BABABAB',S) returns the point where the second AB starts unconditionally from the original.

It can be expressed as S = AB (However, A and B are strings that do not repeat each other)

For any character a, ab = aA' and B = B'b S+S = ABBAB = a'BAB'b.

Therefore, if S is not a repetitive structure, (S+S)[1:-1] is A'BAB' find(A'BAB',S) returns None unconditionally.

2022-09-22 13:01

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656