Trang chủ Tin Học Lớp 8 Số nguyên dương T được gọi là chu kỳ tuần...

Số nguyên dương T được gọi là chu kỳ tuần hoàn của xâu S khác xâu rỗng nếu T nhỏ nhất và khi ghép n xâu giống nhau có độ dài T thì được xâu S. Yêu cầu: Cho trư

Câu hỏi :

Số nguyên dương T được gọi là chu kỳ tuần hoàn của xâu S khác xâu rỗng nếu T nhỏ nhất và khi ghép n xâu giống nhau có độ dài T thì được xâu S. Yêu cầu: Cho trước xâu S khác xâu rỗng. Hãy xác định chu kỳ tuần hoàn của xâu S và cho biết xâu S được ghép từ bao nhiêu xâu giống nhau có độ dài T. Dữ liệu vào: Tệp CHUKY.INP gồm 1 dòng ghi xâu S khác xâu rỗng có độ dài không vượt quá 255. Dữ liệu ra: Tệp CHUKY.OUT gồm 1 dòng ghi số nguyên dương T là chu kỳ tuần hoàn của xâu S và số nguyên dương n là số xâu giống nhau có độ dài T ghép nên xâu S, hai số cách nhau đúng 1 kí tự trống. Ví dụ: CHUKY.INP CHUKY.OUT CHUKY.INP CHUKY.OUT abcabcabcabcabc 3 5 abcdef 6 1

Lời giải 1 :

type int = longint;
var HashT,pow:array[0..300] of int64;
    s:string;
    i,l:byte;
const md = trunc(1e9 + 7);
const base = 37;

function GetHash(i,j:int):int;
begin
    exit((HashT[j] - HashT[i-1]*pow[j-i+1] + md*md) mod md);
end;

function check(r:int):boolean;
var i,p:int;
begin
    p:=GetHash(1,r);
    i:=r;
    while (i <= l) do
        begin
            if GetHash(i-r+1,i) <> p then
                exit(false);
            inc(i,r);
        end;
    exit(true);
end;

begin
    readln(s);
    l:=length(s);
    pow[0]:=1;
    for i:=1 to l do
        pow[i]:= (pow[i-1]*base) mod md;
    for i:=1 to l do
        HashT[i]:=(HashT[i-1]*base + ord(s[i]) - 96) mod md;
    for i:=1 to l do
        if l mod i = 0 then
            if check(i) then
                begin
                    writeln(i,' ',l div i);
                    exit;
                end;
end.

Thảo luận

-- https://hoidap247.com/cau-hoi/2798586
-- giúp với ạ

Lời giải 2 :

Số nguyên dương T được gọi là chu kỳ tuần hoàn của xâu S khác xâu rỗng nếu T nhỏ nhất và khi ghép n xâu giống nhau có độ dài T thì được xâu S. Yêu cầu: Cho trước xâu S khác xâu rỗng. Hãy xác định chu kỳ tuần hoàn của xâu S và cho biết xâu S được ghép từ bao nhiêu xâu giống nhau có độ dài T. Dữ liệu vào: Tệp CHUKY.INP gồm 1 dòng ghi xâu S khác xâu rỗng có độ dài không vượt quá 255. Dữ liệu ra: Tệp CHUKY.OUT gồm 1 dòng ghi số nguyên dương T là chu kỳ tuần hoàn của xâu S và số nguyên dương n là số xâu giống nhau có độ dài T ghép nên xâu S, hai số cách nhau đúng 1 kí tự trống.

Bạn có biết?

Tin học, tiếng Anh: informatics, tiếng Pháp: informatique, là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng (ảo). Với cách hiểu hiện nay, tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin.

Nguồn : Wikipedia - Bách khoa toàn thư

Tâm sự 8

Lớp 8 - Năm thứ ba ở cấp trung học cơ sở, học tập bắt đầu nặng dần, sang năm lại là năm cuối cấp áp lực lớn dần nhưng các em vẫn phải chú ý sức khỏe nhé!

Nguồn : ADMIN :))

Liên hệ hợp tác hoặc quảng cáo: gmail

Điều khoản dịch vụ

Copyright © 2021 HOCTAPSGK