Ước chung của chuỗi
Xem PDF
Đ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
xyztOutput
1Note
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
aaOutput
2Note
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
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.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.