Link Sub: http://www.spoj.com/PTIT/problems/P147PROH/
Người Gửi: Darkness
- Problem:
Bài toán đặt ra là cho trước các cặp xâu ký tự, đều chỉ bao gồm các chữ cái viết thường, hay xác định xem mỗi cặp xâu có được tạo ra từ cùng một bộ ký tự giống nhau hay không. Chú ý: các ký tự lặp cũng phải được xem xét. Ví dụ: “abc”và “aabbbcccc” không được xem là tạo nên bởi cùng một bộ ký tự vì xâu thứ 2 các chữ cái được lặp lại nhiều lần hơn.
Input
Gồm nhiều bộ test, mỗi bộ test gồm hai dòng ghi hai xâu cần kiểm tra, chỉ bao gồm các ký tự viết thường và không quá 1000 ký tự. Input kết thúc khi gặp hai dòng ghi chữ END.
Output
Với mỗi bộ test, ghi ra màn hình thứ tự bộ test và kết quả bài toán (same hoặc different).
Example:
Với mỗi bộ test, ghi ra màn hình thứ tự bộ test và kết quả bài toán (same hoặc different).
Input
testing
intestg
abc
aabbbcccc
abcabcbcc
aabbbcccc
abc
xyz
END
END
Output:
Case 1: same
Case 2: different
Case 3: same
Case 4: different
- Solution:
Áp dụng bảng mã ASCII: - Tạo 2 mảng rỗng >122 phần tử = 0;
- Duyệt từng xâu và đánh dấu các ô thứ [i=ASCII(char)]++;
- So sánh hai mảng sau khi đã đánh dấu;
- Code:
C++:
https://ideone.com/7LKhrh
#include <iostream>
#include <string>
using namespace std;
int main ()
{
//IN;
string A, B;
int case_i=0;
while (1)
{
cin>>A>>B;
if (A=="END" && B=="END") break;
case_i++;
//OUT;
int arrA[128], arrB[128];
for (int i=32; i<=126; i++)
{
arrA[i]=0;
arrB[i]=0;
}
int lenA=A.length();
int lenB=B.length();
for (int i=0; i<lenA; i++)
{
int cs=A[i]-0;
arrA[cs]++;
}
for (int i=0; i<lenB; i++)
{
int cs=B[i]-0;
arrB[cs]++;
}
int kt=1;
for (int i=97; i<=122; i++)
{
if (arrA[i]!=arrB[i])
{
kt=0;
break;
}
}
if (kt==1) cout<<"Case "<<case_i<<": same"<<endl;
else cout<<"Case "<<case_i<<": different"<<endl;
}
return 0;
}