Ước chung của chuỗi

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

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.

Yêu cầu: Bạn được cho 2 chuỗi \(S_1\) và \(S_2\), hãy đếm xem chúng có tất cả bao nhiêu ước chung?

Input

Dòng đầu tiên chứa chuỗi \(S_1\).
Dòng thứ hai chứa chuỗi \(S_2\).
Cả 2 chuỗi đều gồm các chữ cái thường, độ dài 2 chuỗi không quá \(10^5\) ký tự.

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

Note

Chuỗi xyztxyzt có 2 chuỗi ước là: xyzt và xyztxyzt; Chuỗi xyzt có 1 chuỗi ước là: xyzt nên có 1 chuỗi ước chung là xyzt

Test 2

Input

aaaa
aa

Output

Note

Chuỗi aaaa có 3 chuỗi ước là: a, aa và aaaa; Chuỗi aa có 2 chuỗi ước là: a và aa nên có 2 chuỗi ước chung là a và aa

Bình luận

-2

hoquyanhnho 9:28 a.m. 22 Tháng 12, 2022

var
s,st,sm,s1,tg:ansistring;
i,d:longint;
begin
readln(s);
readln(st);
while ( ( s[1]=' ' )) do delete(s,1,1);
while ( s[length(s)]=' ' ) do delete(s,length(s),1);
while ( pos(#32#32,s) > 0 ) do delete(s,pos(#32#32,s),1);
while ( ( st[1]=' ' )) do delete(st,1,1);
while ( st[length(st)]=' ' ) do delete(st,length(st),1);
while ( pos(#32#32,st) > 0 ) do delete(st,pos(#32#32,st),1);
if ( length(s) > length(st) )then
begin
tg:=s;
s:=st;
st:=tg;
end;
d:=0;
for i:=1 to length(s) do
begin
if ( length(st) mod i= 0) then
begin
s1:=copy(s,1,i);
sm:='';
while ( length(sm)<length(s)) do sm:=sm+s1;
if ( sm=s) then inc(d);
end;
end;
writeln(d);
end.

1 bình luận nữa