P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P156SUME/ 1. Đề bài P156SUME spoj Một chuỗi a được gọi là ước của chuỗi b nếu tồn tại một số nguyên dương x sao cho khi ta viết x lần chuỗi a thì sẽ thu được chuỗi b. Ví dụ chuỗi “abab” có 2 ước là “ab” và ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P156SUME/
1. Đề bài P156SUME spoj
Một chuỗi a được gọi là ước của chuỗi b nếu tồn tại một số nguyên dương x sao cho khi ta viết x lần chuỗi a thì sẽ thu được chuỗi b. Ví dụ chuỗi “abab” có 2 ước là “ab” và “abab”.
Bạn được cho 2 cho 2 chuỗi s1 và s2, hãy đếm xem chúng có tất cả bao nhiêu ước chung?
Input
Dòng đầu tiên là 1 chuỗi s1, dòng thứ 2 là chuỗi s2.
Cả 2 chuỗi đều gồm các chữ cái thường, độ dài 2 chuỗi không quá 105.
Output
In ra một số nguyên là kết quả của bài toán.
Example
Test 1:
Input:
xyztxyzt
xyzt
Output:
1
Test 2:
Input:
aaa
aa
Output:
1
2. Hướng dẫn giải P156SUME spoj PTIT
– Gọi n1, n2 là độ dài của 2 xâu s1, s2.
– độ dài ước của xâu sẽ là [1..độ dài xâu], mà ở bài này ta cần xâu chung, như vậy ta chỉ cần xét các xâu có độ dài từ [1..min(n1,n2)]. và xâu có độ dài i có khả năng là ước của xâu khi n1 mod i=0 và n2 mod i = 0.
– Xét mỗi độ dài xâu ước, hãy kiểm tra xem xâu có độ dài i có phải là ước hay không? và kiểm tra ước trên s1, s2 giống nhau không.
– Đếm kết quả bài toán…
3. Code tham khảo P156SUME spoj PTIT
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | const fi='; nmax=100000; type data=longint; var f:text; n1,n2:data; s1,s2:ansistring; procedure docfile; begin assign(f,fi); reset(f); readln(f,s1); readln(f,s2); n1:=length(s1); n2:=length(s2); close(f); end; function min(a,b:data):data; begin if a<b then exit(a); exit(b); end; procedure xuli; var i,j:data; st1,st2,x1,x2:ansistring; res:data; begin res:=0; for i:=1 to min(n1,n2) do if (n1 mod i = 0) and (n2 mod i=0) then begin st1:=copy(s1,1,i); st2:=copy(s2,1,i); if st1<>st2 then continue; x1:='; for j:=1 to n1 div i do x1:=x1+st1; if x1<>s1 then continue; x2:='; for j:=1 to n2 div i do x2:=x2+st2; if x2<>s2 then continue; inc(res); end; writeln(res); end; begin docfile; xuli; end. |
