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à “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á 10⁵.

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:

Test 2:

Input:

aaa

Output:

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

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.

P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi