[Lập trình newbie] Mỗi ngày một bài toán (số 14)

Góc học tập Lập trình
1

Hi all, ,mấy ngày qua mình bận với mấy cái đồ án môn học hè quá nên không ra kịp bài số 14. Hôm nay trở lại chào đón sự thay đổi của HKT ta làm bài sau nhé :D.
Bài toán:
Vị Giám đốc công ty XYZ cần gửi một văn bản quan trọng tới một đối tác của mình. Văn bản là một xâu S các chữ cái la tinh in thường. Để bảo mật nội dung văn bản, ông Giám đốc gửi 2 bức thư. Bức thư thứ nhất là phần đầu Sb của xâu S, bức thư thứ 2 là phần cuối Se của S. Hai bức thư Sb và Se đảm bảo đầy đủ nội dung của S, tuy nhiên có thể một phần cuối của Sb có thể được viết lặp lại trong phần đầu của Se, song số kí tự được viết lặp lại không biết trước.
Ví dụ: với văn bản S=’truongnguyenduquannhat’ tạo ra hai bức thư:

Sb=truong**ngueNdu
**ngueNduquanNhat=Se=
Sb=’truongnguyendu’ và Se=’nguyenduquannhat’
Yêu cầu: Cho hai xâu Sb và Se, hãy xác định một xâu S có thể là nội dung của bức thư sao cho độ dài của xâu S là ngắn nhất.
Dữ liệu
Dòng đầu chứa xâu Sb, dòng thứ hai chứa xâu Se. Mỗi xâu có độ dài không quá 250.
Kết quả
Ghi ra độ dài của xâu S tìm được.
Ví dụ
**Dữ liệu
truongnguyendu
nguyenduquannhat
**Kết quả
22
****Chúc vui vẻ, mình luyện công đây :brick:

2

Lâu rồi mình cũng ko code , chỉ nêu cách giải sơ sơ thôi ^^!

Dùng 2 con trỏ *p , *q bám vào 2 đầu chuỗi sb và se. Dùng 1 biến length để lưu chiều dài kết quả ( length ban đầu = 0 ).
Dùng vòng lặp cho *p đi dần về phía cuối chuỗi sb. Mỗi bước đi ta so sánh ký tự trong *p với ký tự đầu của chuỗi se.

  • Nếu không trùng , tăng length lên 1 , đi tiếp.
    -Nếu trùng , dùng vòng lặp lần lượt so sánh tương ứng ký tự tiếp theo xem nó có trùng với ký tự tiếp theo của chuỗi se không
    • nếu cứ trùng hòai cho đến cuối chuỗi sb thì kết quả sẽ là kq= length + lengthOfSe
    • nếu chưa đến cuối chuỗi se mà có ký tự ko trùng thì cho *q bám lại đầu chuỗi se , break vòng lặp.
3

Ý tưởng của mình :
Viết 1 hàm trích xuất chuỗi gồm n kí tự cuối của Sb và đầu Se và so sánh.
gọi vị trí bắt đầu lấy chuỗi của Sb là L.
L được tính bằng cách lấy ở giữa sâu Sb đầu tiên, nếu không trùng thì ban đầu L=(L+lenght(Sb))/2,sau đó nếu vẫn không trùng thì = (L trước + L hiện tại )/2 trùng thì tiếp tục L=n/2.
cuối cùng sẽ tìm được n.

Y chang cái tìm kiếm nhị phân ý :smiley:

4

Test No 1:
Input:
aaaaaaaaa
aaaaaaaaa
Output = 9 hay 10 hay 17 hay 18 ?

Test No 2:
Input
ThisIsTheTest
ThisIsTheTest
Output = 13, đúng ko ?

5

Dùng thuật toán của bạn kengo14

#include <stdio.h>
#include <string.h>
int chuoicon(char Se[],char Sb[],int i)
{
int j=strlen(Sb)-1;
for (;i>=0&&j>=0;i--,j--)
if (Se*!=Sb[j])
return 0;
return 1;
}
int xuly(char Sb[],char Se[])
{
int i,j=strlen(Sb)-1,p;
for (i=0;i<strlen(Se);i++)
{
if (i==strlen(Sb)-1) return i;
p=i;
}
return p;
}
void main()
{
char Sb[250],Se[250];
gets(Sb);
gets(Se);
int p=xuly(Sb,Se),i=0;
while(i<strlen(Sb))
printf("%c",Sb[i++]);
while(p++<strlen(Se))
printf("%c",Se[p]);
}
6

vậy là ko cần in cái tin nhắn đó ra fai ko?

#include "stdafx.h"
#include <conio.h>
#include <stdio.h>
#include <string.h>
void main()
{
char sb[250],se[250];
int i,j,kq;
printf("nhap:
");
flushall();
gets(sb);
gets(se);
int dem1=strlen(sb);
int dem2=strlen(se);
j=0;
for(i=0;i<=dem1;i++)
{
if(i==dem1) break;
if(sb*==se[j])
{
j++;
}
else j=0;
}
kq=dem1+dem2-j;
printf("
%d",kq);
getch();
}
7

[QUOTE=11520447;72365]vậy là ko cần in cái tin nhắn đó ra fai ko?
[/QUOTE]
Ọc, mình in bà cái chuỗi đó ra rồi, chậc kệ :smiley: