## 10298 - Power Strings

Moderator: Board moderators

Lon
New poster
Posts: 7
Joined: Sat Jan 31, 2004 12:55 pm

### 10298

who can me why time limiit exceed!!!

#include<stdio.h>
#include<string.h>
void main()
{
char ch[1000001];
int in,len,i,j,sum,sum1,ans,count,h;
while(scanf("%s",ch)==1)
{
h=count=sum=sum1=0;
len=strlen(ch);
if(ch[0]=='.')
break;
for(i=1;i<=len;i++)
{
h=sum1=count=0;
sum+=ch[i-1]-'0';
j=1;
for(j;j<=len;)
{
while((count++)<i&&(j<=len))
{
if(ch[count-1]==ch[j-1])
sum1+=ch[j-1]-'0';
j++;
}
if(sum==sum1)
{
count=sum1=0;
ans=i;
h++;
}
else
break;

}
if((len-(h*i))==0)
{
printf("%d\n",h);
break;
}
}
}
}
my name is Lon

jura
New poster
Posts: 4
Joined: Thu Jan 02, 2003 11:00 pm
Location: Croatia
you use brute-force and that's not good enough for very long strings. you have to think of something faster

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 10298 - Power Strings

Can anyone tell me that, is it possible to pass the time limit using brute force in this problem? I tried brute force but got TLE. Or is there any sort of algorithm for this type of problems? Please someone reply.
May be tomorrow is a better day............

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10298 - Power Strings

There's Knuth-Morris-Pratt algorithm. Find using it position of the first occurrence of s in string s*s.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 10298 - Power Strings

mf, I have a silly question. What I knew was this algorithm can be used to find the occurence of a pattern in a string. But how can i use this to find a substring in a string when i dont know the substring? Can you explain it more please
May be tomorrow is a better day............

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10298 - Power Strings

The pattern is string s - the input string.
The string to search the pattern in is s*s, where * is concatenation (as in problem statement).

If s occurs at position k (1-based) in s*s, then the answer is length(s) / k.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 10298 - Power Strings

I have got it, everything is clear. Thanks a lot
May be tomorrow is a better day............

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 10298 - Power Strings

Thanks mf, got AC. But one more thing. Sorry to bother you, but can you explain how and why this approach works?
May be tomorrow is a better day............

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10298 - Power Strings

Hmm, isn't it obvious?

Consider string t obtained from s by a cyclic shift of s by k characters right. How to determine for which values of k, the strings t and s are equal? By definition of equality, it's when s = t = s[(i+k)%n], for 0<=i<n. You can get rid of that modulus by simply concatenating s with itself, and it becomes a regular substring search problem, solved by KMP.

And the smallest such cyclic shift k is exactly equal to length of smallest periodic prefix of s. Number of repetitions of this prefix (which is what the problem asks for) is just length of s divided by length of this prefix.

dodouuu
New poster
Posts: 9
Joined: Tue Mar 24, 2009 7:50 pm

### Re: 10298 - Power Strings

mf wrote:Hmm, isn't it obvious?

Consider string t obtained from s by a cyclic shift of s by k characters right. How to determine for which values of k, the strings t and s are equal? By definition of equality, it's when s = t = s[(i+k)%n], for 0<=i<n. You can get rid of that modulus by simply concatenating s with itself, and it becomes a regular substring search problem, solved by KMP.

And the smallest such cyclic shift k is exactly equal to length of smallest periodic prefix of s. Number of repetitions of this prefix (which is what the problem asks for) is just length of s divided by length of this prefix.

You help me a lot! Thank you very much.

logiclord
New poster
Posts: 2
Joined: Tue Mar 12, 2013 5:57 pm

### Re: 10298 - Power Strings

I am trying a variation with kmp. I calculate Prefix table and tries to infer length from table directly.

My logic is that eventually prefix table should have a sequence of x1,x2,x3.....xN,1,2,3,4,5,6,7,8.....Y

I tried to detect xN and conclude power of string from that. I am not able to understand what is wrong in this approach.

Code: Select all

``````
#include<set>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<string>
#include<map>
#include<sstream>
#include<functional>

using namespace std;

char data[1000005];
int table[1000001];

void myfillTables(int num)
{
memset(table,0,sizeof(table));
table[0] = 0;
table[1] = 0;
int i;
for(int j=2;j<=num; j++)
{
i = table[j-1];
while(1)
{
//cout<<i<<endl;
if(data[i] == data[j-1])
{
table[j] = i+1;
break;
}
else if(i>0)
{
i = table[i];
}
else
{
table[j] = 0;
break;
}
}
}
}

int main()
{
while(gets(data) && !(data[0]=='.' && data[1]=='\0'))
{
int len = strlen(data);
myfillTables(len);
int i, first = len;
for(i=0; i<=len; i++)
{
if(i<len && table[i] == table[i+1]-1 && table[i]>0)
{
first = i-1;
i++;
while(i<=len && table[i]==table[i-1]+1)
{
i++;
}
if(i<=len)
first = len;
}
}
if(len%first==0)
printf("%d\n",len/first);
else
puts("1");
}
return 0;
}

``````
I have tried many test cases and they seems to work.

abcd
aaaa
ababab
abcabababcababdf
abcabababcabab
.

Can someone give me a critical test case for my approach

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10298 - Power Strings

input:

Code: Select all

``````lrbblrbblrbblrbblrbblrbblrbb
bhcdarzbhcdarzbhcdarz
kkyhidd
cdx
mowfrxmowfrxmowfrxmowfrxmowfrxmowfrxmowfrxmowfrxmowfrxmowfrx
ybldbefybldbef
rcbynecdyrcbynecdyrcbynecdyrcbynecdyrcbynecdy
xxxxxxx
klorelklorelklorelklorelklorelklorel
mpapmpapmpapmpapmpapmpapmpapmpap
wkhopwkhopwkhopwkhopwkhopwkhopwkhopwkhop
coqhnwnkucoqhnwnkucoqhnwnkucoqhnwnkucoqhnwnkucoqhnwnkucoqhnwnku
hsqmgbbhsqmgbbhsqmgbbhsqmgbbhsqmgbbhsqmgbbhsqmgbbhsqmgbbhsqmgbb
ccccc
jivswmdkjivswmdk
bxixmvtbxixmvt
bljptnsnbljptnsnbljptnsnbljptnsnbljptnsnbljptnsnbljptnsnbljptnsn
zqfjzqfjzqfjzqfjzqfjzqfjzqfj
ooooooooo
bcnuvq
fbfb
qxwpqcaceqxwpqcaceqxwpqcaceqxwpqcaceqxwpqcace
hzvfrkmlhzvfrkmlhzvfrkmlhzvfrkmlhzvfrkmlhzvfrkmlhzvfrkml
zjkpqpxrzjkpqpxrzjkpqpxrzjkpqpxrzjkpqpxrzjkpqpxrzjkpqpxrzjkpqpxrzjkpqpxr
kitzyxkitzyxkitzyxkitzyx
bhhkicqbhhkicqbhhkicqbhhkicqbhhkicq
endtomfgdendtomfgdendtomfgdendtomfgdendtomfgdendtomfgdendtomfgdendtomfgdendtomfgd
wwwwwwwwww
gpxiqvgpxiqvgpxiqvgpxiqvgpxiqv
ytdytdytd
gdewhtgdewhtgdewhtgdewhtgdewht
iohordtiohordtiohordtiohordtiohordtiohordtiohordtiohordtiohordt
vvvvvvvvv
sssssss
pqoqmsbpqoqmsbpqoqmsb
guwguwguwguwguw
yqxnzlgdgwyqxnzlgdgwyqxnzlgdgwyqxnzlgdgwyqxnzlgdgwyqxnzlgdgwyqxnzlgdgwyqxnzlgdgwyqxnzlgdgwyqxnzlgdgw
trwbtrwbtrwbtrwbtrwbtrwbtrwbtrwbtrwbtrwb
uumoqcduumoqcduumoqcduumoqcduumoqcd
betokybetokybetokybetokybetokybetokybetoky
oachwdvmxxoachwdvmxxoachwdvmxxoachwdvmxxoachwdvmxxoachwdvmxxoachwdvmxxoachwdvmxxoachwdvmxxoachwdvmxx
ryxlmndqturyxlmndqturyxlmndqturyxlmndqturyxlmndqturyxlmndqturyxlmndqturyxlmndqturyxlmndqturyxlmndqtu
agmleagmleagmleagmleagmleagmleagmleagmleagmle
uk
ibxibxibx
umeumeumeumeumeumeumeumeumeume
eyateyateyateyateyateyateyateyateyat
mymymymymymymymymymy
ajxlogajxlogajxlogajxlogajxlog
qfmzhl
hjouvsuyhjouvsuyhjouvsuyhjouvsuyhjouvsuy
payulyepayulyepayulyepayulyepayulye
uotehzriiuotehzriiuotehzriiuotehzriiuotehzriiuotehzriiuotehzriiuotehzriiuotehzrii
skpggskpggskpggskpggskpggskpggskpggskpgg
bipzzrzucbipzzrzucbipzzrzucbipzzrzucbipzzrzucbipzzrzucbipzzrzucbipzzrzuc
mludfymludfymludfy
rrrrr
wwwww
iooobppl
lwplwplwplwplwplwplwplwplwp
vwdtxvwdtxvwdtxvwdtxvwdtxvwdtxvwdtxvwdtxvwdtxvwdtx
myppphmyppphmyppphmyppphmyppphmyppphmyppphmyppph
xnspusgdhxnspusgdhxnspusgdh
xqmbfjxxqmbfjxxqmbfjx
vudjsuyiby
mwsiqyoygmwsiqyoygmwsiqyoygmwsiqyoygmwsiqyoygmwsiqyoyg
ymzevypzvymzevypzvymzevypzvymzevypzvymzevypzvymzevypzvymzevypzvymzevypzvymzevypzvymzevypzv
gebeocfugebeocfugebeocfu
sxdixtigsisxdixtigsisxdixtigsisxdixtigsisxdixtigsisxdixtigsisxdixtigsisxdixtigsisxdixtigsisxdixtigsi
hkchzhkchzhkchzhkchzhkchzhkchzhkchz
lilrjqlilrjqlilrjqlilrjqlilrjqlilrjqlilrjqlilrjqlilrjqlilrjq
xztqxztqxztqxztqxztqxztqxztqxztq
vbspkyhsvbspkyhsvbspkyhsvbspkyhsvbspkyhs
bppkqbppkqbppkqbppkq
ddbuotbbqcddbuotbbqcddbuotbbqcddbuotbbqcddbuotbbqcddbuotbbqcddbuotbbqcddbuotbbqc
vvv
xjujjddnxjujjddnxjujjddnxjujjddnxjujjddnxjujjddn
eiqvdgai
wcwcwcwcwcwcwcwcwcwc
ubwewpjvy
hljxehljxehljxehljxehljxehljxehljxe
piwuqzdzubpiwuqzdzub
bzvafsbzvafsbzvafsbzvafsbzvafs
pqwupqwupqwupqwupqwupqwupqwupqwupqwu
fwovyddw
vburcvburcvburcvburc
gyjgfdxvtn
neslsplwuneslsplwuneslsplwuneslsplwuneslsplwuneslsplwu
ppppp
lzlzlzlz
nhkwnhkwnhkwnhkwnhkw
anltanltanltanltanltanlt
iiiiiiii
cddscddscddscddscddscddscddscdds
oyveguroyveguroyveguroyveguroyveguroyvegur
cs
oxeqmrjooxeqmrjooxeqmrjooxeqmrjooxeqmrjo
gggg
lkobmeahkglkobmeahkglkobmeahkg
nnnnnnnnn
hhshhshhs
ymqpymqpymqpymqpymqp
lrlrlrlrlrlrlrlr
nynynynynynyny
zrzrzrzr
asjeuygaasjeuygaasjeuygaasjeuygaasjeuygaasjeuygaasjeuygaasjeuygaasjeuygaasjeuyga
ububububububub
pnipni
wwwwwww
qsjxvkqdorqsjxvkqdorqsjxvkqdorqsjxvkqdorqsjxvkqdorqsjxvkqdorqsjxvkqdorqsjxvkqdorqsjxvkqdorqsjxvkqdor
vrwctdsnvrwctdsnvrwctdsnvrwctdsn
ggggg
pkpkpkpk
pgpg
rbfcrbfcrbfc
qifpgyqifpgyqifpgyqifpgyqifpgy
rrrrrrrrrrrrrr
xsnvucftpxsnvucftpxsnvucftpxsnvucftpxsnvucftpxsnvucftp
tgttgttgt
xxx
pycfgcpycfgcpycfgcpycfgcpycfgcpycfgcpycfgc
unublmo
ttttttttt
klefszbeklefszbeklefszbeklefszbeklefszbeklefszbeklefszbeklefszbeklefszbe
ampetvhqampetvhqampetvhqampetvhq
djeqvuygpndjeqvuygpn
zzzzzzz
rpjrpj
axdpcwmjaxdpcwmjaxdpcwmjaxdpcwmjaxdpcwmjaxdpcwmjaxdpcwmj
mskskfomskskfomskskfomskskfomskskfomskskfo
ewxgxnnoewxgxnnoewxgxnnoewxgxnnoewxgxnnoewxgxnno
ltwjwnnvltwjwnnvltwjwnnv
jckdmeoujckdmeoujckdmeoujckdmeoujckdmeou
hyvhyvhyvhyvhyvhyvhyvhyvhyvhyv
vwujbqvwujbqvwujbqvwujbqvwujbqvwujbqvwujbq
pitcvogrpitcvogrpitcvogrpitcvogrpitcvogrpitcvogrpitcvogrpitcvogr
ddd
hrhrhrhrhrhrhrhrhrhr
sycqsycq
leewhxteleewhxteleewhxteleewhxteleewhxte
aqwqwpqhsaqwqwpqhsaqwqwpqhsaqwqwpqhsaqwqwpqhsaqwqwpqhsaqwqwpqhsaqwqwpqhsaqwqwpqhsaqwqwpqhs
bnvfgvjbnvfgvjbnvfgvjbnvfgvjbnvfgvjbnvfgvjbnvfgvj
vvvvvvvvvv
afafafaf
zxlcxdznczxlcxdznczxlcxdznczxlcxdznczxlcxdznczxlcxdznc
jlapopk
fgvicefgvice
mkbljomkbljomkbljomkbljomkbljo
tqvvhbgsdvtqvvhbgsdvtqvvhbgsdvtqvvhbgsdvtqvvhbgsdvtqvvhbgsdvtqvvhbgsdvtqvvhbgsdvtqvvhbgsdv
hesnkqxhesnkqx
rqirqirqirqirqi
vmhlvmhlvmhlvmhlvmhlvmhlvmhlvmhl
brybrybrybrybrybry
heyentmroheyentmro
eyqcrgluaieyqcrgluaieyqcrgluaieyqcrgluaieyqcrgluaieyqcrgluaieyqcrgluaieyqcrgluaieyqcrgluaieyqcrgluai
veixwjjveixwjjveixwjjveixwjj
op
jjjj
xhxdipfzw
ybgfylqvjybgfylqvjybgfylqvjybgfylqvjybgfylqvj
arvrlyauarvrlyauarvrlyauarvrlyauarvrlyauarvrlyauarvrlyauarvrlyauarvrlyauarvrlyau
drcnjkpdrcnjkpdrcnjkpdrcnjkpdrcnjkpdrcnjkp
lffrkeeclffrkeeclffrkeec
dipufhidjcdipufhidjcdipufhidjcdipufhidjcdipufhidjcdipufhidjcdipufhidjcdipufhidjcdipufhidjcdipufhidjc
hrnxcxmjcxhrnxcxmjcxhrnxcxmjcxhrnxcxmjcxhrnxcxmjcxhrnxcxmjcx
qqqqqq
xdrmgxdrmg
bhbhbh
mwpmhwdvthmwpmhwdvth
queeexgqueeexgqueeexgqueeexg
jigskmvrjigskmvrjigskmvrjigskmvrjigskmvr
fwvrfwvrfwvrfwvrfwvr
wapdtutpbzwapdtutpbzwapdtutpbzwapdtutpbzwapdtutpbzwapdtutpbz
gngngngngngngn
xxxxxx
jngjng
mikjzsdwsmikjzsdwsmikjzsdws
novdruypcnovdruypcnovdruypcnovdruypcnovdruypcnovdruypc
ulkfulkf
mxnafammxnafammxnafammxnafam
pckjcpckjcpckjcpckjcpckjcpckjcpckjcpckjcpckjc
xdrtdgyxdrtdgyxdrtdgyxdrtdgyxdrtdgyxdrtdgyxdrtdgyxdrtdgyxdrtdgyxdrtdgy
scczybnvqqscczybnvqqscczybnvqqscczybnvqqscczybnvqq
cjicjicji
vcnvvcnvvcnvvcnvvcnvvcnv
asidzgwr
tzzwpwm
fjknfjkn
kelhhkelhhkelhhkelhhkelhhkelhh
chpdnlunchpdnlunchpdnlunchpdnlunchpdnlunchpdnlunchpdnlunchpdnlun
pnlgjpnlgjpnlgjpnlgjpnlgjpnlgjpnlgjpnlgjpnlgjpnlgj
kewwuysgefkewwuysgefkewwuysgefkewwuysgef
expmmsbaoexpmmsbaoexpmmsbaoexpmmsbaoexpmmsbaoexpmmsbao
dgzqdgzqdgzqdgzqdgzqdgzqdgzq
qzxuvtqqzxuvtqqzxuvtqqzxuvtqqzxuvtqqzxuvtqqzxuvtq
xbslxbslxbslxbslxbslxbsl
kglzakglza
pdnsjolvypdnsjolvypdnsjolvypdnsjolvypdnsjolvypdnsjolvypdnsjolvypdnsjolvy
xxttqognxxttqognxxttqognxxttqognxxttqognxxttqognxxttqognxxttqognxxttqogn
aiakqlaiakqlaiakqlaiakqlaiakqlaiakql
zkhfzconnmzkhfzconnmzkhfzconnm
kkk
eefsnsmouweefsnsmouweefsnsmouweefsnsmouw
odsgcfoheodsgcfoheodsgcfoheodsgcfoheodsgcfoheodsgcfohe
shmshmshm
wtoaywtoaywtoaywtoaywtoaywtoaywtoaywtoaywtoaywtoay
nojnojnojnojnojnoj
ftqtftqtftqtftqtftqtftqtftqtftqt
bbbbbbbbb
rr
jimqwjimqwjimqwjimqwjimqwjimqwjimqwjimqwjimqw
slgvlcsslgvlcsslgvlcsslgvlcs
b
gwtbgwtbgwtbgwtbgwtbgwtbgwtbgwtbgwtbgwtb
ettwdettwdettwd
nbnbnbnb
vpdjxyuzqvpdjxyuzq
tatbzpcttatbzpcttatbzpct
oofremgfkroofremgfkr
vkzvgbof
gojhdnaywpgojhdnaywpgojhdnaywpgojhdnaywp
itoraaitoraaitoraaitoraaitoraaitoraaitoraaitoraaitoraaitoraa
eeeeeeee
ezwfpdawezwfpdawezwfpdawezwfpdaw
hssvtqtkfv
ljzljzljz
cqxscqxscqxscqxscqxscqxscqxscqxscqxs
qqqqqqqqq
tdmfrtzlqstdmfrtzlqstdmfrtzlqstdmfrtzlqs
ejh
sklfepxcsklfepxcsklfepxcsklfepxcsklfepxc
czczczcz
vdgvdgvdgvdgvdg
bb
swme
lzilzilzilzilzi
tmoikstmoikstmoikstmoikstmoiks
xtgpoxtgpoxtgpoxtgpo
qiysrsqfwqqiysrsqfwqqiysrsqfwqqiysrsqfwq
qnqnqnqnqnqnqnqnqnqn
gdqrnllgdqrnllgdqrnllgdqrnllgdqrnll
eeeeeee
vmwnuufnnvmwnuufnnvmwnuufnnvmwnuufnnvmwnuufnnvmwnuufnnvmwnuufnnvmwnuufnnvmwnuufnnvmwnuufnn
loyvgmliuqloyvgmliuqloyvgmliuqloyvgmliuqloyvgmliuqloyvgmliuqloyvgmliuqloyvgmliuq
dlyavdlyavdlyavdlyav
uaosnluaosnluaosnluaosnluaosnluaosnluaosnluaosnluaosnl
acsvacsv
umoi
cqx
kqwgxyaznkqwgxyaznkqwgxyaznkqwgxyaznkqwgxyazn
aikameybaikameybaikameybaikameybaikameybaikameyb
qbqbqb
aggxaaggxaaggxaaggxaaggxaaggxaaggxaaggxaaggxa
rynqxqqrynqxqqrynqxqqrynqxqqrynqxqqrynqxqqrynqxqqrynqxqq
fotfotfotfot
hvokiiamhvokiiamhvokiiamhvokiiamhvokiiam
mvxmvxmvxmvxmvxmvxmvxmvxmvx
bsbs
i
yxnjcbyxnjcbyxnjcbyxnjcbyxnjcbyxnjcbyxnjcbyxnjcb
rnmixxsrnmixxsrnmixxsrnmixxsrnmixxsrnmixxs
hovengbhovengbhovengbhovengbhovengbhovengbhovengbhovengbhovengbhovengb
qrixqgwdqrixqgwdqrixqgwdqrixqgwdqrixqgwdqrixqgwdqrixqgwd
gxrxkfhigxrxkfhigxrxkfhigxrxkfhigxrxkfhigxrxkfhigxrxkfhi
inhwilkinhwilkinhwilkinhwilkinhwilk
bpeszdigz
xtzqsjxtzqsjxtzqsjxtzqsj
ttttttttt
bmjawwmbmjawwmbmjawwmbmjawwmbmjawwm
nepfdunepfdunepfdu
ucucucucucuc
xmkpvgrrgtxmkpvgrrgtxmkpvgrrgtxmkpvgrrgtxmkpvgrrgtxmkpvgrrgtxmkpvgrrgtxmkpvgrrgt
euragel
capwpbqromcapwpbqromcapwpbqromcapwpbqromcapwpbqromcapwpbqromcapwpbqromcapwpbqromcapwpbqrom
wixwixwixwixwixwixwixwixwix
qkvlfbhwcqkvlfbhwcqkvlfbhwcqkvlfbhwc
pjmrmpjmrmpjmrm
begvsuluqtbegvsuluqtbegvsuluqtbegvsuluqtbegvsuluqtbegvsuluqtbegvsuluqtbegvsuluqt
vkesvvkesvvkesvvkesvvkesvvkesvvkesv
dhvtjmexdhvtjmexdhvtjmexdhvtjmexdhvtjmexdhvtjmexdhvtjmexdhvtjmexdhvtjmexdhvtjmex
bvufdpbvufdpbvufdp
cwncwncwncwn
jtbplyz
icwsoicwsoicwsoicwsoicwsoicwsoicwsoicwsoicwsoicwso
wtqrpywtqrpywtqrpywtqrpy
aaaaa
wgfnwgfnwgfnwgfn
qelofrqelofrqelofrqelofrqelofr
tqiktxitqiktxitqiktxitqiktxitqiktxi
zeqvlq
ooooooooo
bjbrpmixfbjbrpmixf
bstnosvdkbstnosvdkbstnosvdkbstnosvdkbstnosvdkbstnosvdk
cpwsdcpwsdcpwsdcpwsdcpwsdcpwsdcpwsdcpwsdcpwsdcpwsd
xrkxrkxrkxrkxrkxrk
eziowoq
iecwxxbjiecwxxbjiecwxxbjiecwxxbjiecwxxbjiecwxxbj
mkmkmkmkmkmk
ncpmvauqgtncpmvauqgtncpmvauqgtncpmvauqgtncpmvauqgtncpmvauqgtncpmvauqgt
sokbfugjtsokbfugjtsokbfugjt
uqbjclvluqbjclvluqbjclvluqbjclvluqbjclvluqbjclvluqbjclvluqbjclvluqbjclvl
amuamuamuamuamuamu
micnewdox
ufsuevjaxufsuevjax
ivcoivcoivcoivcoivcoivco
frqqwnujfrqqwnujfrqqwnujfrqqwnujfrqqwnujfrqqwnujfrqqwnujfrqqwnuj
oyevslqoyevslqoyevslqoyevslqoyevslqoyevslqoyevslqoyevslqoyevslq
lyskrhlyskrhlyskrhlyskrhlyskrhlyskrhlyskrhlyskrhlyskrhlyskrh
llllll
soxlsoxlsoxlsoxlsoxl
yyf
tozqhmgye
yepfaesjlkyepfaesjlkyepfaesjlkyepfaesjlkyepfaesjlkyepfaesjlkyepfaesjlkyepfaesjlkyepfaesjlk
vdevvdevvdevvdevvdevvdevvdevvdevvdev
lygazxjnlygazxjn
rxhrdyyddqrxhrdyyddqrxhrdyyddqrxhrdyyddqrxhrdyyddqrxhrdyyddqrxhrdyyddqrxhrdyyddqrxhrdyyddqrxhrdyyddq
dododododo
shwxsshwxsshwxs
zjywumzjywum
famxdnxjfamxdnxjfamxdnxjfamxdnxjfamxdnxjfamxdnxj
yirmiyirmiyirmiyirmiyirmiyirmiyirmiyirmiyirmi
rnekxdrnekxdrnekxdrnekxdrnekxdrnekxdrnekxdrnekxdrnekxd
cjfqkkcjfqkkcjfqkkcjfqkkcjfqkk
xuqmszxuqmsz
xxxxxxxxx
kwskwskwskwskwskwskwskwskwskws
iwyfalpeuiwyfalpeuiwyfalpeu
gfrteomgfrteomgfrteomgfrteomgfrteomgfrteomgfrteomgfrteomgfrteom
nnn
nir
lpstosaodqlpstosaodqlpstosaodqlpstosaodqlpstosaodq
kogrfbxtnkogrfbxtnkogrfbxtnkogrfbxtnkogrfbxtnkogrfbxtnkogrfbxtnkogrfbxtnkogrfbxtnkogrfbxtn
bltqtmbltqtmbltqtmbltqtmbltqtmbltqtmbltqtmbltqtmbltqtmbltqtm
ye
ujuiokcujuiokcujuiokcujuiokc
swqyxswqyxswqyxswqyxswqyx
ndxqqsgkndxqqsgkndxqqsgkndxqqsgkndxqqsgkndxqqsgkndxqqsgkndxqqsgkndxqqsgkndxqqsgk
ihbaawihbaawihbaawihbaawihbaawihbaawihbaawihbaawihbaawihbaaw
gagloddkgagloddkgagloddkgagloddkgagloddkgagloddkgagloddk
jizynyoejizynyoe
ozryityozryityozryityozryityozryityozryityozryity
ifximkifximkifximkifximkifximkifximkifximkifximkifximkifximk
okktvusuiokktvusuiokktvusuiokktvusuiokktvusuiokktvusuiokktvusuiokktvusui
ojfckya
yekijksvusyekijksvusyekijksvusyekijksvusyekijksvusyekijksvusyekijksvusyekijksvus
ccccc
avwufavwufavwufavwufavwuf
tajxkitajxkitajxkitajxkitajxki
bxjmbxjmbxjmbxjmbxjmbxjm
wcqqxfbbfwcqqxfbbfwcqqxfbbfwcqqxfbbf
frwkvuuhfrwkvuuhfrwkvuuhfrwkvuuh
difvfkydifvfkydifvfkydifvfky
fiuleafiuleafiulea
aapaaapaaapaaapaaapaaapaaapa
wteswteswteswteswteswteswteswtes
weqfmnmymtweqfmnmymtweqfmnmymtweqfmnmymt
eleinelein
ppppp
pvomquepvomquepvomquepvomquepvomquepvomquepvomquepvomquepvomquepvomque
dmxdmxdmxdmxdmxdmxdmxdmx
n
zqnzqnzqnzqn
axgnjaxgnjaxgnjaxgnjaxgnjaxgnjaxgnjaxgnjaxgnj
xbuusxbuusxbuusxbuusxbuusxbuusxbuusxbuus
mnqwqmnqwqmnqwqmnqwqmnqwqmnqwqmnqwq
akqzqgk
hqfdimnhqfdimnhqfdimnhqfdimnhqfdimnhqfdimnhqfdimnhqfdimnhqfdimnhqfdimn
gggggggg
lorowlorowlorowlorowlorowlorowlorowlorowlorowlorow
gehioxhhgehioxhhgehioxhhgehioxhhgehioxhhgehioxhhgehioxhhgehioxhh
vqvqvqvqvqvqvqvq
wdtksslykwdtksslykwdtksslykwdtksslykwdtksslykwdtksslyk
ataataataataataataataata
pdmyldxupdmyldxupdmyldxupdmyldxupdmyldxu
nnnnnnnn
prruprruprruprruprruprruprruprru
mmmmmmmm
lro
hwoqntchwoqntc
hl
oooooooo
hgsbaecplphgsbaecplphgsbaecplphgsbaecplp
dyvnxmdmf
oplqizoplqizoplqiz
iiiiii
jtimitdjtimitd
iksxjiksxjiksxjiksxjiksxjiksxjiksxjiksxjiksxjiksxj
wmkwabhwmkwabhwmkwabh
ievievievievievievieviev
wcqeqwcqeq
tkydwrbgxtkydwrbgxtkydwrbgxtkydwrbgx
jpalshgejpalshgejpalshgejpalshgejpalshgejpalshgejpalshge
zhhvlxzhhvlxzhhvlx
xdwjccgtdxdwjccgtdxdwjccgtdxdwjccgtdxdwjccgtdxdwjccgtdxdwjccgtdxdwjccgtdxdwjccgtdxdwjccgtd
i
yspqzvuqiyspqzvuqiyspqzvuqi
ptlpvooyptlpvooy
apgvapgvapgvapgvapgvapgvapgv
ooo
s
hhhhhhhhh
fnfnfnfnfnfnfnfnfnfn
jyeeltzaizjyeeltzaizjyeeltzaizjyeeltzaizjyeeltzaizjyeeltzaizjyeeltzaizjyeeltzaizjyeeltzaizjyeeltzaiz
ccozwkccozwkccozwkccozwkccozwkccozwkccozwk
yhzgpqlwfkyhzgpqlwfkyhzgpqlwfkyhzgpqlwfkyhzgpqlwfkyhzgpqlwfkyhzgpqlwfk
ipuujvwtipuujvwtipuujvwtipuujvwtipuujvwtipuujvwtipuujvwtipuujvwtipuujvwt
bznryjdobznryjdobznryjdobznryjdobznryjdobznryjdobznryjdobznryjdobznryjdobznryjdo
vghmyuigvghmyuigvghmyuigvghmyuigvghmyuigvghmyuigvghmyuigvghmyuig
yqjtmyqjtmyqjtmyqjtmyqjtmyqjtmyqjtmyqjtmyqjtmyqjtm
inninninninninninninninninn
mihntkdd
lwnmsxsalwnmsxsalwnmsxsalwnmsxsalwnmsxsalwnmsxsalwnmsxsa
qeldqeldqeldqeldqeld
nnpjfnnpjfnnpjfnnpjfnnpjf
mrnyumrnyu
ww
jpjpjpjpjpjp
hdeavknyhdeavknyhdeavknyhdeavknyhdeavknyhdeavknyhdeavknyhdeavkny
oxhxclqqeoxhxclqqe
avdwzoio
wwxyrhwwxyrhwwxyrhwwxyrhwwxyrhwwxyrhwwxyrhwwxyrhwwxyrhwwxyrh
rdrdrdrdrdrdrd
kduvtkduvtkduvtkduvtkduvtkduvtkduvt
zczufvtvfzczufvtvfzczufvtvfzczufvtvfzczufvtvfzczufvtvfzczufvtvfzczufvtvfzczufvtvfzczufvtvf
ygkygkygkygkygkygkygk
dervvu
eghbctcbeghbctcbeghbctcbeghbctcbeghbctcbeghbctcbeghbctcbeghbctcb
xezrzgxezrzgxezrzgxezrzgxezrzgxezrzgxezrzgxezrzg
fhzafhzafhzafhza
fefefefefefefefe
bbb
fmzjqtlrs
xqiywjobspxqiywjobspxqiywjobspxqiywjobspxqiywjobspxqiywjobspxqiywjobspxqiywjobspxqiywjobspxqiywjobsp
ujlxnujlxnujlxnujlxnujlxnujlxn
durddiydurddiydurddiydurddiydurddiydurddiydurddiydurddiy
qfspvcoulqfspvcoul
drzkmkwdrzkmkwdrzkmkwdrzkmkwdrzkmkwdrzkmkwdrzkmkwdrzkmkw
iqdchghriqdchghriqdchghriqdchghriqdchghriqdchghriqdchghriqdchghriqdchghr
tzdnobqtzdnobqtzdnobqtzdnobqtzdnobqtzdnobqtzdnobq
deqdeqdeqdeqdeqdeq
stmestmestmestmestmestmestmestmestme
cacacaca
ewqmoxkjwpewqmoxkjwpewqmoxkjwpewqmoxkjwpewqmoxkjwpewqmoxkjwpewqmoxkjwp
qorqorqorqorqorqorqorqorqor
xedvywxedvywxedvywxedvywxedvyw
oghotpusoghotpusoghotpusoghotpusoghotpus
iestiestiestiestiestiestiest
rrrrrrrrr
igocfufbubigocfufbubigocfufbubigocfufbubigocfufbubigocfufbubigocfufbubigocfufbubigocfufbub
rrffmwarrffmwarrffmwarrffmwarrffmwa
i
ddddddddd
nzcphkflnzcphkfl
qsqsqsqsqsqsqsqs
dwludsdwludsdwludsdwluds
ungfzoiungfzoiungfzoiungfzoiungfzoi
xifoprwcjzxifoprwcjzxifoprwcjzxifoprwcjzxifoprwcjzxifoprwcjz
xngtacwxngtacw
ypweuxveypweuxveypweuxveypweuxve
bogsfbogsfbogsfbogsfbogsfbogsfbogsf
hipbompufphipbompufphipbompufphipbompufphipbompufphipbompufphipbompufp
kikikikikikikikiki
ghufczmghufczmghufczmghufczmghufczmghufczmghufczm
cgwigcgwigcgwigcgwigcgwigcgwigcgwig
qcteqkbqcteqkbqcteqkbqcteqkbqcteqkbqcteqkb
aaaa
iiiii
qlivnjjqlivnjjqlivnjj
m
ucz
dgztqarsardgztqarsardgztqarsardgztqarsardgztqarsardgztqarsardgztqarsardgztqarsardgztqarsardgztqarsar
w
heyheyhey
hlhlhlhlhlhlhlhlhl
jjjjjjjj
opdopd
lkoelkoelkoelkoelkoelkoelkoe
ynzeynzeynzeynzeynzeynze
aaceazuaaceazuaaceazuaaceazuaaceazuaaceazu
ydypvydypvydypvydypvydypvydypvydypvydypvydypv
yxbyxbyxbyxbyxbyxbyxbyxbyxb
ppuuppuuppuuppuuppuuppuu
tttttttttttttt
tmvtmvtmv
uuvjvahuuvjvahuuvjvahuuvjvahuuvjvahuuvjvah
vv
ss
zkywhmgczkywhmgczkywhmgczkywhmgczkywhmgczkywhmgc
vdcqdpvdcqdpvdcqdpvdcqdpvdcqdp
mxwneikzfmxwneikzfmxwneikzfmxwneikzfmxwneikzfmxwneikzf
antantantantantantantant
pwzvpwzvpwzvpwzv
nvkplpfnvkplpfnvkplpfnvkplpfnvkplpfnvkplpfnvkplpfnvkplpfnvkplpfnvkplpf
txngexrfc
dmuszlobiodmuszlobiodmuszlobiodmuszlobio
kwkxlrxblkwkxlrxbl
tztztztztztztztztz
eqlftxzeqlftxzeqlftxzeqlftxzeqlftxzeqlftxzeqlftxzeqlftxzeqlftxz
kbcsqmnckbcsqmnckbcsqmnckbcsqmnckbcsqmnckbcsqmnckbcsqmnckbcsqmnc
zvr
eupyvdeupyvdeupyvdeupyvdeupyvd
twhpvtwhpvtwhpvtwhpvtwhpvtwhpvtwhpvtwhpvtwhpvtwhpv
w
yl
byubxruwsbyubxruwsbyubxruwsbyubxruwsbyubxruwsbyubxruwsbyubxruws
hxpmjrhfhxpmjrhfhxpmjrhfhxpmjrhfhxpmjrhf
ddd
zbfzbfzbfzbfzbfzbf
dd
bhtaapzsobhtaapzsobhtaapzsobhtaapzsobhtaapzsobhtaapzsobhtaapzso
njpznjpz
eeeeeeeeee
jjjj
jqdjhjqdjhjqdjhjqdjhjqdjhjqdjhjqdjhjqdjhjqdjh
zz
ukfjjzacbpukfjjzacbpukfjjzacbp
oppvoppvoppvoppvoppvoppvoppvoppvoppv
eijpyneijpyn
vuefyvuefyvuefyvuefyvuefyvuefy
bsypjombsypjombsypjombsypjombsypjombsypjombsypjom
rnkirnkirnkirnkirnkirnki
hsvbwczwhsvbwczwhsvbwczwhsvbwczwhsvbwczwhsvbwczw
fvirbosvfvirbosv
fcymdrzqzfcymdrzqzfcymdrzqzfcymdrzqzfcymdrzqzfcymdrzqz
gemgem
ojyjofojyjofojyjofojyjofojyjofojyjofojyjof
wimwimwim
ackack
witxysjqznwitxysjqznwitxysjqzn
pttncjtpttncjtpttncjtpttncjtpttncjt
rtrt
wwojbqhjjf
oacoacoacoacoacoacoacoacoacoac
nnnnnnnnn
ihcsanihcsan
gxdcttnugxdcttnugxdcttnugxdcttnugxdcttnugxdcttnugxdcttnugxdcttnu
fscrwqtyfscrwqty
nnn
wvbqxorwvbqxorwvbqxorwvbqxorwvbqxorwvbqxor
owzowzowzowzowzowzowzowzowz
mdzjlrlcmdzjlrlcmdzjlrlcmdzjlrlc
yoywbmvzhxyoywbmvzhxyoywbmvzhxyoywbmvzhxyoywbmvzhxyoywbmvzhxyoywbmvzhx
nhvivthfnhvivthfnhvivthfnhvivthfnhvivthf
khfxbkhfxbkhfxbkhfxbkhfxbkhfxbkhfxbkhfxbkhfxbkhfxb
quyetwiftquyetwiftquyetwift
sxsx
goqbhxgoqbhxgoqbhxgoqbhxgoqbhxgoqbhxgoqbhx
svzzscq
mszfqmszfqmszfqmszfqmszfqmszfq
mtaemtaemtaemtaemtaemtaemtaemtaemtaemtae
mykcbrzmykcbrzmykcbrzmykcbrzmykcbrzmykcbrzmykcbrzmykcbrz
uhltznluiuhltznlui
kfhkfhkfhkfhkfhkfhkfhkfhkfh
touzgqmeaotouzgqmeaotouzgqmeaotouzgqmeaotouzgqmeaotouzgqmeaotouzgqmeaotouzgqmeaotouzgqmeao
qqqq
mmmmmmmm
hydtuotjyyhydtuotjyyhydtuotjyyhydtuotjyyhydtuotjyyhydtuotjyyhydtuotjyyhydtuotjyyhydtuotjyy
tlknmqdyvtlknmqdyvtlknmqdyvtlknmqdyvtlknmqdyvtlknmqdyvtlknmqdyvtlknmqdyv
bxftbxftbxftbxftbxftbxftbxftbxftbxftbxft
uqastvpuqastvpuqastvpuqastvp
ahpsdifnahpsdifnahpsdifn
fbqafbqafbqafbqafbqafbqafbqafbqafbqafbqa
dfoyhhsxhdfoyhhsxhdfoyhhsxhdfoyhhsxh
dcctcmiudcctcmiudcctcmiudcctcmiudcctcmiudcctcmiudcctcmiudcctcmiudcctcmiudcctcmiu
zeqsjrzeqsjrzeqsjrzeqsjrzeqsjr
zrphfoozrphfoozrphfoo
oyvjdxnwboyvjdxnwboyvjdxnwb
vqzwuprgvqzwuprgvqzwuprgvqzwuprg
sitjpsitjpsitjpsitjpsitjpsitjpsitjpsitjpsitjpsitjp
frifrifrifrifrifrifrifrifrifri
fesfsqfesfsqfesfsqfesfsqfesfsqfesfsq
xekxekxekxek
gmtmvvgf
wspdjwspdjwspdjwspdjwspdjwspdjwspdjwspdjwspdj
jzhwsjzhws
pcafsyaibpcafsyaibpcafsyaibpcafsyaibpcafsyaibpcafsyaibpcafsyaibpcafsyaib
amam
gwbtpqegwbtpqegwbtpqegwbtpqegwbtpqegwbtpqegwbtpqe
nknknknknknknknk
dxguzgcsecdxguzgcsecdxguzgcsecdxguzgcsecdxguzgcsecdxguzgcsecdxguzgcsecdxguzgcsecdxguzgcsecdxguzgcsec
nlizyogwqnlizyogwqnlizyogwq
ifxcthdgifxcthdgifxcthdgifxcthdg
njztlnjztlnjztlnjztlnjztl
nviajsnviajsnviajsnviajsnviajsnviajsnviajs
hkdxlrfhkdxlrfhkdxlrfhkdxlrfhkdxlrfhkdxlrf
hmxmhmxmhmxmhmxmhmxm
mhvodmhvodmhvodmhvodmhvodmhvodmhvod
dvfdvfdvfdvf
ofofofof
mlmlmlml
xvrojacjpxvrojacjp
beubeubeubeu
cbmzgzwwcbmzgzwwcbmzgzwwcbmzgzww
vtlzeivxyvtlzeivxyvtlzeivxyvtlzeivxyvtlzeivxy
aaaaa
zosdikzosdikzosdikzosdik
lwltxirlwltxirlwltxir
oytnfeieep
gvgvqjfgvgvqjfgvgvqjfgvgvqjfgvgvqjfgvgvqjfgvgvqjfgvgvqjfgvgvqjfgvgvqjf
sntfiqnsntfiqnsntfiqnsntfiqnsntfiqnsntfiqn
xpxp
czznfdcczznfdc
kkkkkkkkk
hxhxhxhxhx
zyhozyhozyhozyhozyhozyhozyhozyhozyhozyho
wjcxfbobwjcxfbobwjcxfbob
cvehbcvehbcvehbcvehbcvehbcvehbcvehbcvehb
nnnnnnnnnn
gggg
jpeiysbmrjpeiysbmrjpeiysbmr
qssfvoyxqssfvoyxqssfvoyxqssfvoyxqssfvoyxqssfvoyxqssfvoyx
glmglmglmglmglm
gfgihqzna
dmzqcpdmzqcpdmzqcpdmzqcpdmzqcpdmzqcpdmzqcp
udjucudjucudjucudjucudjuc
jiml
qpdzhfnheqpdzhfnheqpdzhfnheqpdzhfnheqpdzhfnheqpdzhfnhe
sudvjlrgsudvjlrgsudvjlrg
avavavavavavav
ehlrqgjhmjehlrqgjhmjehlrqgjhmjehlrqgjhmjehlrqgjhmjehlrqgjhmjehlrqgjhmjehlrqgjhmj
yzztjsnyzztjsnyzztjsnyzztjsnyzztjsnyzztjsn
yagetjfyagetjfyagetjfyagetjfyagetjfyagetjfyagetjfyagetjfyagetjfyagetjf
exqexqexq
ia
ojhjhgiojhjhgiojhjhgiojhjhgi
cpgrniysdcpgrniysdcpgrniysdcpgrniysdcpgrniysdcpgrniysd
tptptptptptp
hwhphwhphwhphwhphwhphwhphwhp
ioopxxvgxioopxxvgxioopxxvgxioopxxvgxioopxxvgxioopxxvgx
ovabovabovab
tgjs
zszszszszszszszszs
zzweizzweizzweizzweizzwei
xixixixixixixi
qqqqqqqqqqqq
ee
hiddqmxrhiddqmxr
jwtiwjwtiwjwtiwjwtiwjwtiwjwtiw
gckdldgckdldgckdldgckdldgckdldgckdldgckdld
tkctkctkctkctkctkctkctkc
fhzikpfhzikpfhzikpfhzikpfhzikpfhzikpfhzikpfhzikpfhzikpfhzikp
hhhhhhhhhh
qfbbbtrhqfbbbtrhqfbbbtrhqfbbbtrhqfbbbtrh
nifnmbaqnifnmbaqnifnmbaqnifnmbaqnifnmbaqnifnmbaqnifnmbaqnifnmbaqnifnmbaq
yjrgvgdyjrgvgd
mlirnjmlirnjmlirnjmlirnjmlirnjmlirnjmlirnjmlirnj
aedetokjclaedetokjclaedetokjclaedetokjclaedetokjclaedetokjclaedetokjcl
naqzrzuanaqzrzuanaqzrzuanaqzrzuanaqzrzua
pqnpqn
cicicicicicicici
llnpedbllnpedbllnpedbllnpedbllnpedbllnpedbllnpedb
oyyczqdspxoyyczqdspxoyyczqdspxoyyczqdspxoyyczqdspxoyyczqdspxoyyczqdspxoyyczqdspx
bkjqjtsbkjqjtsbkjqjtsbkjqjtsbkjqjtsbkjqjtsbkjqjtsbkjqjts
cfkrwcfkrwcfkrwcfkrwcfkrwcfkrwcfkrwcfkrwcfkrwcfkrw
ygygygygygyg
faqfaqfaqfaqfaq
tyitteutyitteutyitteutyitteu
kmgegginkmgegginkmgegginkmgegginkmgegginkmgegginkmgegginkmgegginkmgegginkmgeggin
kjyksbyxdkjyksbyxdkjyksbyxdkjyksbyxdkjyksbyxdkjyksbyxd
wkwkwkwkwkwkwkwk
fylzbalqjpfylzbalqjp
xxxx
zyvzyv
nyimezramy
xwtaxesgurxwtaxesgurxwtaxesgurxwtaxesgurxwtaxesgurxwtaxesgur
fifififi
fspssfspss
wzzzlykevhwzzzlykevhwzzzlykevh
geqmahltgeqmahltgeqmahltgeqmahltgeqmahltgeqmahltgeqmahltgeqmahlt
oooooooo
iiiiiiiiiiiiiiii
fczgfczgfczgfczgfczgfczgfczg
tbkayttbkayttbkayt
zdonzdonzdon
azjwpczxkwazjwpczxkwazjwpczxkwazjwpczxkwazjwpczxkwazjwpczxkw
aaaa
ccccccc
nvggteiynvggteiynvggteiynvggteiynvggteiynvggteiy
cpwdacpwdacpwdacpwdacpwdacpwda
evrqrsjevrqrsjevrqrsjevrqrsjevrqrsjevrqrsjevrqrsj
jwxffkaltjwxffkaltjwxffkaltjwxffkaltjwxffkaltjwxffkaltjwxffkaltjwxffkaltjwxffkaltjwxffkalt
bulybulybulybulybulybulybulybuly
udcudcudcudcudc
glowdggxbglowdggxbglowdggxbglowdggxbglowdggxbglowdggxbglowdggxbglowdggxb
zwzwzwzwzwzwzwzw
xogufhotixogufhotixogufhotixogufhotixogufhotixogufhotixogufhotixogufhoti
eryvoeryvoeryvoeryvoeryvoeryvoeryvoeryvoeryvoeryvo
cbnljkoahcbnljkoahcbnljkoahcbnljkoahcbnljkoahcbnljkoahcbnljkoahcbnljkoahcbnljkoah
ibwwhqibwwhqibwwhqibwwhqibwwhqibwwhq
hwzxhwzx
pppppppppp
dujixytdujixytdujixyt
jjqzijjqzijjqzijjqzijjqzijjqzijjqzijjqzi
eeeeeee
wccwcc
ddqjuijzduddqjuijzduddqjuijzduddqjuijzduddqjuijzduddqjuijzduddqjuijzdu
tclemwwltclemwwltclemwwl
nkvwinkvwinkvwinkvwinkvwinkvwinkvwinkvwinkvwinkvwi
oyctoyct
nzxoetyionzxoetyionzxoetyionzxoetyionzxoetyionzxoetyionzxoetyionzxoetyionzxoetyionzxoetyio
sorrbvosorrbvosorrbvosorrbvosorrbvosorrbvosorrbvosorrbvo
ll
lqgluzdgoelqgluzdgoelqgluzdgoelqgluzdgoelqgluzdgoe
kaatpdohtgkaatpdohtgkaatpdohtg
dddddddd
llllllll
bpuhabpuhabpuhabpuhabpuhabpuhabpuhabpuhabpuha
fxwkcafxwkcafxwkca
bnrgebbmd
uuuu
y
nnkpesubonnkpesubonnkpesubonnkpesubo
rrrrrrrr
uquququququququququq
uedg
ydsaydsaydsaydsaydsaydsaydsa
eoboeoboeoboeoboeoboeoboeoboeoboeobo
jcgzglqjvkjcgzglqjvkjcgzglqjvkjcgzglqjvkjcgzglqjvkjcgzglqjvk
mucqdlubpmucqdlubpmucqdlubpmucqdlubpmucqdlubpmucqdlubpmucqdlubp
qyfqyfqyfqyfqyfqyfqyfqyfqyfqyf
wmhfoogxwmhfoogxwmhfoogx
gugugugugugugugu
swdwmiswdwmiswdwmiswdwmiswdwmi
jzujzujzujzujzujzujzujzujzu
uuuu
www
ee
ufctcjufctcjufctcjufctcj
rkiwhrkiwhrkiwhrkiwhrkiwhrkiwhrkiwhrkiwhrkiwh
repreprepreprepreprep
eeeee
yirqvxyirqvxyirqvxyirqvxyirqvxyirqvxyirqvxyirqvxyirqvx
rwbmbmeprwbmbmeprwbmbmeprwbmbmeprwbmbmep
zeyvkrzajzzeyvkrzajzzeyvkrzajzzeyvkrzajz
ttttttttt
kwvkwvkwvkwvkwvkwvkwvkwvkwv
wawa
nmnrnmnrnmnrnmnrnmnrnmnr
icygxjxyliicygxjxyliicygxjxyliicygxjxyliicygxjxyli
btvbbtvbbtvbbtvbbtvbbtvb
zngxnrzngxnr
glujfcmelglujfcmelglujfcmelglujfcmelglujfcmel
kmctltuekmctltuekmctltuekmctltuekmctltuekmctltuekmctltuekmctltuekmctltuekmctltue
kjuxprmipkjuxprmipkjuxprmipkjuxprmipkjuxprmipkjuxprmipkjuxprmipkjuxprmip
ajyinmmyxd
fefefefefefefefefefe
yzqtlzqi
xybmnxybmnxybmnxybmnxybmnxybmn
llmxllmxllmxllmx
bvqalaqxx
jedippvooijedippvooijedippvooi
gucguc
oooooooooo
rfwsrwkqurfwsrwkqurfwsrwkqu
fftqwinmxv
dtdtdtdtdtdtdt
tmvtmv
atytrill
tpvlofyaetpvlofyaetpvlofyaetpvlofyaetpvlofyaetpvlofyaetpvlofyaetpvlofyaetpvlofyaetpvlofyae
wyttlofiwyttlofiwyttlofiwyttlofiwyttlofiwyttlofi
kghekghekghekghe
pletgvpletgvpletgvpletgvpletgv
jvpkajvpkajvpkajvpkajvpkajvpkajvpkajvpkajvpkajvpka
yietvyietv
dfknlutlodfknlutlodfknlutlodfknlutlo
seenuxxpseenuxxpseenuxxpseenuxxpseenuxxpseenuxxpseenuxxpseenuxxpseenuxxp
rysrysrysrysrysrysrysrys
xldpkivxvxldpkivxvxldpkivxv
pvhpvhpvhpvhpvhpvhpvhpvhpvhpvh
bezoawnpkbezoawnpkbezoawnpkbezoawnpkbezoawnpkbezoawnpk
kpbummzkpbummz
hayfhayfhayfhayfhayfhayf
ugawcbugawcbugawcbugawcbugawcbugawcbugawcbugawcbugawcbugawcb
rr
hrkhrkhrkhrkhrkhrkhrkhrkhrk
xsdrgsrmxsdrgsrmxsdrgsrmxsdrgsrmxsdrgsrmxsdrgsrmxsdrgsrm
mpfzibmpfzibmpfzibmpfzibmpfzib
xinxinxinxinxinxinxinxinxin
gbjngbjngbjngbjngbjngbjn
rvrvrvrvrv
bmbmbmbm
ffffffff
isdisdisdisdisd
lpavlpavlpavlpavlpavlpavlpav
kkkkk
qphekqphekqphekqphekqphekqphekqphekqphekqphekqphek
iaiaiaiaiaiaiaiaiaia
maemae
qqqqqqq
tttttt
ggvdxfggvdxfggvdxfggvdxf
cdajcdajcdajcdajcdajcdajcdajcdajcdajcdaj
qgvqpeqgvqpeqgvqpeqgvqpeqgvqpeqgvqpeqgvqpeqgvqpe
izaabbizaabb
wbbtwbbtwbbt
aaa
cwnoiacwnoiacwnoiacwnoia
vvd
xlzxlcyg
hhhhhhh
nzpgkrfahnnzpgkrfahnnzpgkrfahnnzpgkrfahnnzpgkrfahnnzpgkrfahnnzpgkrfahnnzpgkrfahnnzpgkrfahnnzpgkrfahn
byjhzlebyjhzlebyjhzle
bwbwbwbwbwbwbw
fkxmkfkxmkfkxmkfkxmkfkxmkfkxmkfkxmkfkxmk
jbijbijbijbijbijbijbijbijbi
pwccwqgpwccwqgpwccwqgpwccwqgpwccwqgpwccwqgpwccwqg
nwmrhyufmnwmrhyufmnwmrhyufmnwmrhyufmnwmrhyufmnwmrhyufmnwmrhyufmnwmrhyufm
ys
gbuh
dbdbdbdbdbdbdbdbdb
dmxjjyyfkdmxjjyyfkdmxjjyyfkdmxjjyyfkdmxjjyyfkdmxjjyyfk
il
ievc
igzrtrvuhcigzrtrvuhc
ccccccc
akakakak
dyvdyvdyvdyv
szxnecsmszxnecsmszxnecsmszxnecsmszxnecsmszxnecsm
gengengen
vhvhvhvhvh
jmukyjmukyjmukyjmukyjmukyjmukyjmukyjmukyjmukyjmuky
dcsutmudcsutmu
yvumiosmyvumiosmyvumiosmyvumiosm
gpsblegpsblegpsblegpsblegpsblegpsblegpsblegpsble
gvbahlqcxrgvbahlqcxrgvbahlqcxrgvbahlqcxrgvbahlqcxrgvbahlqcxrgvbahlqcxr
qebfvgpvjcqebfvgpvjcqebfvgpvjc
upqfvnlbupqfvnlbupqfvnlbupqfvnlbupqfvnlbupqfvnlbupqfvnlbupqfvnlbupqfvnlbupqfvnlb
dsatudsatudsatudsatudsatu
vldcvldcvldcvldc
xuxudcpvwxuxudcpvwxuxudcpvwxuxudcpvwxuxudcpvwxuxudcpvwxuxudcpvw
bcbodjebcbodjebcbodjebcbodjebcbodjebcbodjebcbodjebcbodje
ecxgpttuviecxgpttuviecxgpttuviecxgpttuviecxgpttuviecxgpttuvi
ecokeefaksecokeefaksecokeefaksecokeefaksecokeefaksecokeefaksecokeefaksecokeefaksecokeefaks
ttsfttsfttsf
igfgmigfgmigfgmigfgmigfgmigfgmigfgmigfgm
gryqusgryqusgryqusgryqusgryqusgryqus
iefiefiefiefiefief
ibcnpvjibcnpvjibcnpvjibcnpvj
jkjkjkjkjkjkjkjkjk
stcpuiguydstcpuiguyd
eeeee
jjjjjj
rmmhbkql
xzopssgmcxzopssgmcxzopssgmcxzopssgmcxzopssgmcxzopssgmc
cswxcswxcswx
wheibqvitwheibqvitwheibqvitwheibqvit
evzevptn
ckpknjhmhckpknjhmhckpknjhmhckpknjhmhckpknjhmhckpknjhmhckpknjhmh
ogs
pzrwxypzrwxypzrwxypzrwxypzrwxy
cpocpocpocpocpocpocpo
wzgiqtxzwzgiqtxzwzgiqtxzwzgiqtxzwzgiqtxz
getxkmmkbgetxkmmkbgetxkmmkbgetxkmmkbgetxkmmkbgetxkmmkbgetxkmmkbgetxkmmkb
anbumanbumanbumanbumanbumanbumanbumanbum
gtrgutpgtrgutpgtrgutpgtrgutpgtrgutp
lalalala
ovccwcqaycovccwcqayc
eieieieieieieieieiei
lzkgsqlzkgsqlzkgsq
iiii
tfxstfxstfxstfxstfxstfxstfxs
u
zoqzoqzoq
yjwgkayjwgkayjwgka
lbfdesljgglbfdesljgglbfdesljgglbfdesljgg
alxvjnalxvjnalxvjnalxvjnalxvjnalxvjn
ggggggg
egpmspgdegpmspgdegpmspgdegpmspgdegpmspgdegpmspgdegpmspgdegpmspgdegpmspgd
ignctignctignctignctignctignctignctignct
aonazkxi
igrbkigrbkigrbkigrbk
wsfexiogod
aaaaaaaaaa
qiqiqiqiqiqiqiqi
tlatjkztlatjkztlatjkztlatjkztlatjkztlatjkztlatjkztlatjkztlatjkztlatjkz
lbbhtholbbhtho
ezezezezezezezez
jqjqjqjq
capqsidubcapqsidubcapqsidub
coqnsrulacoqnsrulacoqnsrulacoqnsrulacoqnsrula
rof
rpivrkkherpivrkkherpivrkkherpivrkkherpivrkkherpivrkkherpivrkkhe
yxzyxzyxzyxzyxz
pvmhmjvpvbpvmhmjvpvbpvmhmjvpvbpvmhmjvpvbpvmhmjvpvbpvmhmjvpvb
hfkyusvnehfkyusvnehfkyusvne
jcijajmbz
iwzfnuiwzfnuiwzfnuiwzfnuiwzfnuiwzfnuiwzfnuiwzfnuiwzfnu
goaqmukhjrgoaqmukhjrgoaqmukhjrgoaqmukhjr
auojwzauojwzauojwzauojwz
yhnjfyhnjfyhnjfyhnjfyhnjfyhnjfyhnjfyhnjfyhnjfyhnjf
slxorslxorslxorslxorslxorslxorslxorslxorslxor
kzlwkzlwkzlwkzlwkzlw
naanuqzq
qqifqqifqqifqqif
upifnwyaupifnwyaupifnwyaupifnwyaupifnwyaupifnwyaupifnwya
ayhj
jjjjjjj
gklyckqgklyckqgklyckqgklyckqgklyckqgklyckqgklyckqgklyckqgklyckq
wwwww
skrzxpzackskrzxpzackskrzxpzack
rlx
rxrxrx
i
uvynrrxlbquvynrrxlbquvynrrxlbquvynrrxlbquvynrrxlbquvynrrxlbquvynrrxlbq
gkdkugkdkugkdkugkdku
nsmaqdavnsmaqdavnsmaqdavnsmaqdavnsmaqdavnsmaqdav
anfxlupercanfxlupercanfxlupercanfxlupercanfxlupercanfxlupercanfxluperc
nlqnlqnlqnlqnlq
ctvrindictvrindictvrindi
kaqvkaqvkaqvkaqvkaqvkaqv
aaaaa
uryuryuryuryuryuryuryuryuryury
ivitivit
jqcghktnjqcghktnjqcghktnjqcghktnjqcghktnjqcghktnjqcghktnjqcghktn
wfbocfuchowfbocfuchowfbocfuchowfbocfuchowfbocfuchowfbocfuchowfbocfucho
mmwmmwmmwmmwmmw
eeeeee
oapqiwbblwoapqiwbblwoapqiwbblwoapqiwbblw
deygksktdeygkskt
uwxuwxuwxuwxuwxuwx
iwjhklwbtiwjhklwbtiwjhklwbt
wgaaqfwgaaqfwgaaqfwgaaqfwgaaqfwgaaqfwgaaqf
lqkyklqkyklqkyklqkyklqkyklqkyklqkyk
gpgwkostwfgpgwkostwfgpgwkostwfgpgwkostwf
gapkgapkgapkgapkgapk
mzorfemzorfemzorfemzorfemzorfemzorfemzorfe
ofih
zumjkgezumjkgezumjkge
ldtldtldtldtldtldt
fno
cltisrxxbecltisrxxbecltisrxxbecltisrxxbecltisrxxbe
dhdormdhdormdhdormdhdormdhdormdhdormdhdormdhdormdhdormdhdorm
xeftuxxeftuxxeftux
osxsdtbxkosxsdtbxkosxsdtbxkosxsdtbxk
oehfkoloehfkoloehfkol
xthwympskxthwympsk
aibsnut
tevtevtevtevtevtev
ciznigkcociznigkcociznigkcociznigkco
cycycy
oaoychlycoaoychlycoaoychlycoaoychlycoaoychlycoaoychlycoaoychlycoaoychlycoaoychlyc
wbwbwbwbwbwbwbwb
ofepuowofepuowofepuowofepuowofepuowofepuowofepuowofepuowofepuow
mouomouomouomouomouomouomouo
dkbzmgdkbzmgdkbzmgdkbzmgdkbzmgdkbzmgdkbzmg
lzsflzsflzsflzsflzsflzsflzsflzsflzsf
miaccqmiaccqmiaccqmiaccqmiaccqmiaccqmiaccq
vyppvyppvyppvyppvyppvypp
rsiursiursiu
vtqqvdrnvtqqvdrnvtqqvdrnvtqqvdrnvtqqvdrnvtqqvdrnvtqqvdrn
bzrddtwbzrddtwbzrddtwbzrddtw
twiiatwiiatwiiatwiiatwiiatwiiatwiiatwiiatwiiatwiia
s
zpzpzpzpzpzpzp
hhhhhhh
mgdyphxmgdyphxmgdyphxmgdyphxmgdyphxmgdyphxmgdyphxmgdyphxmgdyphx
dbibudbibudbibudbibudbibudbibudbibu
cmyxoscnucmyxoscnucmyxoscnu
mcmcmcmcmcmc
qdqdqdqdqdqdqd
upocbreupocbreupocbreupocbreupocbreupocbreupocbre
aaa
ddddd
ctneictneictneictneictnei
rvrvrvrvrvrvrvrvrvrv
yrsgyrsgyrsgyrsgyrsg
vvpyvvpyvvpyvvpyvvpyvvpyvvpyvvpyvvpy
wcywcywcywcywcywcywcywcy
gsgsgsgsgs
ninnbhninnbhninnbhninnbhninnbhninnbhninnbhninnbhninnbhninnbh
usglrvusglrvusglrvusglrvusglrvusglrvusglrvusglrvusglrvusglrv
gdejggdejg
ihqrpkihqrpkihqrpkihqrpkihqrpkihqrpkihqrpkihqrpk
ajdajdajd
llvhfeswllvhfeswllvhfeswllvhfeswllvhfeswllvhfeswllvhfeswllvhfeswllvhfesw
ahahahahahahah
qlnyuw
lblbdwesjlblbdwesjlblbdwesjlblbdwesjlblbdwesjlblbdwesjlblbdwesjlblbdwesj
ewewewewewewewewewew
ohohohohohohohohoh
jqjqjqjqjq
jlcjlcjlcjlcjlcjlcjlcjlcjlcjlc
yxulagmdcryxulagmdcr
gbsfmcvgbsfmcvgbsfmcvgbsfmcvgbsfmcvgbsfmcvgbsfmcvgbsfmcv
mfgmtpxmfgmtpxmfgmtpxmfgmtpxmfgmtpxmfgmtpxmfgmtpxmfgmtpxmfgmtpx
fywzfywzfywz
hycmpyxxbrhycmpyxxbrhycmpyxxbr
.
``````
AC output:

Code: Select all

``````7
3
1
1
10
2
5
7
6
8
8
7
9
5
2
2
8
7
9
9
1
2
5
7
9
4
5
9
10
5
3
5
9
9
7
3
5
10
10
4
5
7
10
10
9
1
3
10
9
10
5
1
5
5
9
8
8
3
5
5
1
9
9
10
8
3
3
1
6
10
3
10
7
10
8
5
4
8
3
6
1
10
1
7
2
5
9
1
4
1
6
5
4
5
6
8
8
6
1
5
4
3
9
3
5
8
7
4
10
7
2
7
10
4
5
4
2
3
5
14
6
3
3
7
1
9
9
4
2
7
2
7
6
6
3
5
10
7
8
3
10
2
5
10
7
10
4
6
1
2
5
9
2
5
8
6
2
10
4
1
4
1
5
10
6
3
10
6
6
2
3
2
4
5
5
6
7
6
2
3
6
2
4
9
10
5
3
6
1
1
2
6
8
10
4
6
7
7
6
2
8
9
6
3
3
4
6
3
10
6
8
9
2
9
4
1
10
3
4
2
3
2
1
4
10
8
4
1
3
9
9
4
1
5
4
5
2
1
5
5
4
4
10
5
7
10
8
4
9
2
1
1
5
6
3
9
8
4
5
9
2
1
8
6
10
7
7
5
1
4
9
5
3
6
8
1
9
9
4
3
8
7
10
3
4
1
10
4
5
4
5
5
1
9
2
6
10
6
1
6
6
7
3
9
6
1
2
2
6
8
9
10
6
5
1
1
9
9
2
10
5
3
2
6
9
9
5
2
9
10
3
9
3
1
5
10
10
1
4
5
10
10
7
2
7
10
8
1
8
5
5
5
6
4
2
4
4
3
7
8
4
2
5
10
8
1
4
9
8
7
8
1
10
8
10
8
8
6
8
5
8
8
8
1
2
1
8
4
1
3
6
2
10
3
8
2
4
7
3
10
1
3
2
7
3
1
9
10
10
7
7
9
10
8
10
9
1
7
5
5
2
2
6
8
2
1
10
7
7
10
7
1
8
8
4
8
3
1
10
6
8
2
8
9
7
6
9
4
7
9
5
5
7
9
9
5
1
9
2
8
4
5
6
2
4
7
7
9
7
7
6
4
5
3
1
1
10
1
3
9
8
2
7
6
6
9
9
6
14
3
6
2
2
6
5
6
8
4
10
1
4
2
9
9
8
1
5
10
1
1
7
5
3
6
2
7
2
10
4
9
2
3
9
2
6
2
7
6
6
2
6
2
7
3
2
3
5
2
1
10
9
2
8
2
3
6
9
4
7
5
10
3
2
7
1
6
10
8
2
9
9
4
8
9
8
10
4
3
10
4
10
5
3
3
4
10
10
6
4
1
9
4
2
8
2
7
8
10
3
4
5
7
6
5
7
4
4
4
2
4
4
5
5
4
3
1
10
6
2
2
9
5
10
3
8
10
4
3
7
5
1
7
5
1
6
3
7
8
6
10
3
1
4
6
6
7
6
3
1
9
5
7
12
2
2
6
7
8
10
10
5
9
2
8
7
5
2
8
7
8
8
10
6
5
4
10
6
8
2
4
2
1
6
4
2
3
8
8
16
7
3
3
6
4
7
6
6
7
10
8
5
8
8
8
10
9
6
2
10
3
8
7
2
7
3
10
2
10
8
2
5
3
8
8
9
3
1
4
1
4
8
10
1
7
9
6
7
10
3
8
5
9
4
3
2
4
9
7
5
9
5
4
9
9
2
6
5
6
2
5
10
8
1
10
1
6
4
6
1
3
2
10
3
1
7
2
1
10
6
4
5
10
2
4
9
8
3
10
6
2
6
10
2
9
7
5
9
6
5
4
8
5
7
5
10
10
2
7
6
4
10
8
2
3
3
4
1
1
7
10
3
7
8
9
7
8
1
1
9
6
1
1
2
7
4
4
6
3
5
10
2
4
6
8
7
3
10
5
4
7
8
6
9
3
8
6
6
4
9
2
5
6
1
6
3
4
1
7
1
5
7
5
8
8
10
5
4
2
10
3
4
7
1
3
3
4
6
7
9
8
1
4
1
10
8
10
2
8
4
3
5
1
7
5
6
3
1
9
4
4
10
9
5
1
4
7
1
7
9
5
3
1
3
1
7
4
6
7
5
3
6
5
10
2
8
7
5
6
4
2
6
3
7
7
4
5
7
1
3
6
1
5
10
3
4
3
2
1
6
4
3
9
8
9
7
10
7
9
7
6
3
7
4
10
1
7
7
9
7
3
6
7
7
3
5
5
10
5
9
4
8
5
10
10
2
8
3
9
7
1
8
10
9
5
10
2
8
9
3
3
``````
Check input and AC output for thousands of problems on uDebug!

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

### Re: 10298 - Power Strings

mf wrote:There's Knuth-Morris-Pratt algorithm. Find using it position of the first occurrence of s in string s*s.
I used the same strategy, but still got TLE, I believe my algorithm is O(n):

Code: Select all

``````inline int GetLargestN(const char* cs)
{
string s(cs);
string ss(s, 1); ss += s; ss += s[0];

int len = s.length();
int pos = ss.find(s);

return len/(pos+1);
}``````
http://www.cplusplus.com/reference/string/string/find/ string::find should be O(n)

I Believe I Can - leestime.com

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

### Re: 10298 - Power Strings

OK. I switched to use the native C function strstr, and it got accepted, which does NOT make too much sense!

http://stackoverflow.com/questions/19506571
I Believe I Can - leestime.com

numan947
New poster
Posts: 3
Joined: Mon Nov 03, 2014 9:46 am

### Re: 10298 - Power Strings

I have got a lot of TLE while trying to solve this problem. After trying for a certain period I came up with a HIGHLY modified brute force algorithm to solve this problem. I saw this thread's discussion about the KMP algorithm & tried to learn it. The problem is I don't know how to use this KMP algorithm to solve this problem! Then I went to http://e-maxx.ru/algo/prefix_function
website as I heard it's a good source. The problem is the portion where the article discussed the process called "Compression Line". As the original site is russian & I used google translator to translate it, some portion wasn't finely translated. So, I didn't understand that portion. Could some one please explain how this portion>>//Consider it the last value, ie \ Pi [n-1], and introduce notation k = n - \ pi [n-1]. We show that if ndivisible by k, then it kwill be a long answer, otherwise effective compression does not exist, and the answer is n.//>>from the website is working(i.e. what does that actually mean?!)?
and also I want to know if this problem can be solved using Z-function.