Xin hỏi các hàm xử lý xâu trong C,C++

**longcheng** · 01-06-2014, 01:18 PM

Như tít ạ, trước dùng pascal có 1 số hàm rất hay, giờ chuyển sang C,C++ hơi bỡ ngỡ chút, mình muốn tìm các hàm trong C++ dùng ở kiểu string [IMG]images/smilies/smile.png[/IMG], hoặc trong C dùng ở char (hàm dùng ở string thì tốt hơn ạ)
hàm có chức năng giống hàm pos(s1,s2) trong pascal
Hàm POS(st1,st2): hàm cho tavị trí tìm thấy đầu tiên của xâu s1 trong xâu s2.
Ví dụ: POS(‘Lam’,‘Le Thanh Lam’) = 10;

Hàm chuyển từ số sang xâu nữa ạ
Thủ tục STR(value, st): Thủ tục này thực hiện việc chuyển đối giá trị kiểu số(value) sang dạng xâu ký tự và gán cho biến st.
Ví dụ: n là một só nguyên có giá trị: n:=150;
STR(n:5,st) sẽ cho kết quả xâu st là: st=’ 150’;

Tại mình đã làm 1 bài = pascal

Mã:

Uses crt;Var  st,s:ansistring;  i,n:longint;BEGIN  Clrscr;  Readln(n);  For i:=1 to n do    Begin      Str(i,s);      st:=st+s;    End;  Write(pos(s,st));  readln;END.

mình muốn chuyển sang C,C++
Mình đã thử = google, chắp vá lung tung các loại, sử dụng kiểu string của STL trong C++
thì được bài này, chạy ra kết quả đúng nhưng thời gian hơi lâu so với chuơng trình pascal trên

Mã:

#include <iostream>#include <stdio.h>#include <string>#define MAX 100000 main(){  std::string st;  long i,n;  char s[MAX];  scanf("%ld",&n);  for (i=1; i<=n; i++)  {    snprintf(s,79,"%ld",i);    st=st+s;  }  printf("%ld",st.find(s)+1);}

trong này mình dùng printf, scanf hình như nhanh hơn là cin,cout nên mới ra nửa C, nửa C++ như vậy ợ.

View more random threads:

**seotop1** · 01-06-2014, 01:59 PM

Thực ra bài này ko nên làm như bạn đã làm [IMG]images/smilies/smile.png[/IMG]
Cần động não chút.

Còn

trong này mình dùng printf, scanf hình như nhanh hơn là cin,cout

thì đúng.

**drspiller12345** · 01-06-2014, 03:29 PM

st = st + s
thì st + s là 1 chuỗi mới, st được gán vào chuỗi này, thời gian lâu hơn gấp đôi so với st += s

nếu ghép chuỗi nhiều thì nên sử dụng stringstream, ở đây là ostringstream (tương tự như StringBuilder bên Java):

Mã:

#include <sstream> // std::ostringstream std::ostringstream oss;for (...) { s = ...; oss << s; }printf("%s", oss.str.c_str()); //oss là std::ostringstream, oss.str là std::string, oss.str.c_str() là const char*

Hoặc nếu biết trước độ dài của chuỗi sau cùng, thì có thể gọi st.reserve(độ dài chuỗi sau cùng + 1) rồi gọi st += s.

Mã:

st.reserve(... + 1);for (...) { s = ...; st += s; }printf("%s", st.c_str());

Vì chuỗi trong C++ là mảng ký tự kết thúc bằng ký tự '\0', mỗi khi mảng đầy thì sẽ được chuyển sang mảng mới có khả năng chứa gấp đôi số ký tự của mảng cũ. Kích thước ban đầu của mảng là 0. Trong chương trình trên thì st sẽ tăng kích thước từ 0 lên 1, 2, 4, 8, 16, ... mỗi lần tăng kích thước phải copy mảng cũ sang mảng mới, tổng cộng nếu + thêm n ký tự (độ dài chuỗi sau cùng là n) thì thật ra sẽ tốn 3n phép gán. Gọi st.reserve(n+1) để đặt kích thước của mảng là n+1 (+1 cho ký tự '\0') thì sẽ bảo đảm mảng ko bị copy sang mảng mới, tốn còn n phép gán thay vì 3n.

còn tại sao là 3n thì gu gồ "amortized cost of dynamic table insertion" là biết...

**thuyduong** · 01-06-2014, 03:43 PM

Bài này giải đúng thì O(logn), ko cần O(nlogn).

**honganh** · 02-06-2014, 03:51 PM

Cảm ơn các bạn nhiều lắm [IMG]images/smilies/smile.png[/IMG], mình đang ngâm cứu [IMG]images/smilies/daydreaming.gif[/IMG]
à thế trong C++ có hàm nào giống STR không các bạn nhỉ ? , dùng cái snprintf kiểu gì ấy.
mình cần chuyển số sang kiểu string như pascal ạ, vì cũng thấy nhiều bài cần cái này.

- - - Nội dung đã được cập nhật ngày 02-06-2014 lúc 08:51 PM - - -

À cho mình hỏi nữa là nếu muốn in ra xâu ra không muốn dùng cout thì dùng các gì tiện mà hay nhỉ ?
trước mình dùng for (i=0; i<st.length();i++) printf("%c",st[i]); , cơ mà lại hơi dài.
với cả mình hay dùng cái getline(cin,st) để đọc 1 xâu, nhưng đọc trên mạng thấy có người bảo không nên vì nó làm gì vùng đệm đó mình chả nhớ nữa. Thế giờ mình nên dùng cái nào để đọc và in xâu cho chuẩn các bạn nhỉ ?
sorry mình hỏi hơi nhiều tại gà quá

**namthanh08** · 02-06-2014, 03:58 PM

à thế trong C++ có hàm nào giống STR không các bạn nhỉ ?

Dùng std::stringstream đê.
Với lại nếu đua speed thì ko nên dùng C++ sẽ bị lỗ. (cái này chắc khỏi cần bàn)

in ra xâu ra không muốn dùng cout

Why?

với cả mình hay dùng cái getline(cin,st) để đọc 1 xâu, nhưng đọc trên mạng thấy có người bảo không nên vì nó làm gì vùng đệm đó mình chả nhớ nữa

Dùng cái cin.getline(char*, int, [char delim]) chống buffer overrun hay std::string là ngon rồi.

**thanhtungbooking** · 02-06-2014, 04:46 PM

Gửi bởi prog10

Dùng std::stringstream đê.
Với lại nếu đua speed thì ko nên dùng C++ sẽ bị lỗ. (cái này chắc khỏi cần bàn)

Why?

Dùng cái cin.getline(char*, int, [char delim]) chống buffer overrun hay std::string là ngon rồi.

Hình như cả C code chạy cũng chậm hơn so với pascal đúng không bác nhỉ ?

cái mình ko dùng cout là tưởng cout xuất ra chậm hơn printf, nãy vừa thử lại thì printf lại chậm hơn, có lẽ cái này mình cần xem lại
đã thử code này và thấy C chậm hơn C++ ,C++ chậm hơn pascal
Mình thử cái bài in ra số nguyên tố thuộc [a;b] ấy ạ

Mã:

#include <iostream>#include <memory.h>#define MAX 200000 using namespace std;main(){  short int check[MAX];  long a=1,b=MAX,i,j;  memset(check,1,sizeof(check));  check[1]=0;  //cin>>a>>b;  for (i=2; i<=b; i++)    if (check[i])      for (j=i; j<=b/i; j++) check[i*j]=0;  for (i=a; i<=b; i++)    if (check[i]) cout<<i<<endl;}

Mã:

#include <stdio.h>#include <memory.h>#define MAX 200000 main(){  short int check[MAX];  long a=1,b=MAX,i,j;  memset(check,1,sizeof(check));  check[1]=0;  //scanf("%d %d",&a,&b);  for (i=2; i<=b; i++)    if (check[i])      for (j=i; j<=b/i; j++) check[i*j]=0;  for (i=a; i<=b; i++)    if (check[i]) printf("%d 
",i);}

không biết mình có làm sai gì không chứ trước giờ mình luôn nghĩ là C luôn phải nhanh hơn C++, mình chạy 2 code trên code::block nó có cái tính giờ.
Còn vụ cin.getline thì ý bạn bảo thế là dùng getline(cin,st) với st là kiểu string thì sẽ không lỗi à ?, hay kể cả đọc char hay string cũng nên dùng cin.getline(char*, int, [char delim]) nhỉ ?

**phuongnguyen** · 02-06-2014, 04:54 PM

a/ Thực ra code này không chuẩn.
1. Để ý là có phép chia, đây là một phép tính rất tốn thời gian (chắc chắn là dịch thẳng từ Pascal, vì bước nhảy trong Pascal có giới hạn), ta có thể thay bằng phép cộng.
2. Còn 1 chỗ không chuẩn nữa: phải là i<=sqrt((double)b, lúc này có thể đưa biểu thức căn ra khỏi vòng lặp, etc.
3. Thực ra sàng trong [a,b] ko cần sàng full, nhưng cứ cài sàng full cho chuẩn đã, khi đã hiểu thì mới qua sàng phân đoạn.

b/

hay kể cả đọc char hay string cũng nên dùng cin.getline(char*, int, [char delim])

Đối số là char* cơ mà [IMG]images/smilies/biggrin.png[/IMG]
std::string thì ko hề có khái niệm nhập có limit (có lẽ là ko cần đặt ra vấn đề buffer overrun với std::string?)

**lehoangtanh.lk** · 02-06-2014, 05:09 PM

Gửi bởi INTP

st = st + s
thì st + s là 1 chuỗi mới, st được gán vào chuỗi này, thời gian lâu hơn gấp đôi so với st += s

nếu ghép chuỗi nhiều thì nên sử dụng stringstream, ở đây là ostringstream (tương tự như StringBuilder bên Java):

Mã:

#include <sstream> // std::ostringstream std::ostringstream oss;for (...) { s = ...; oss << s; }printf("%s", oss.str.c_str()); //oss là std::ostringstream, oss.str là std::string, oss.str.c_str() là const char*

Hoặc nếu biết trước độ dài của chuỗi sau cùng, thì có thể gọi st.reserve(độ dài chuỗi sau cùng + 1) rồi gọi st += s.

Mã:

st.reserve(... + 1);for (...) { s = ...; st += s; }printf("%s", st.c_str());

Vì chuỗi trong C++ là mảng ký tự kết thúc bằng ký tự '\0', mỗi khi mảng đầy thì sẽ được chuyển sang mảng mới có khả năng chứa gấp đôi số ký tự của mảng cũ. Kích thước ban đầu của mảng là 0. Trong chương trình trên thì st sẽ tăng kích thước từ 0 lên 1, 2, 4, 8, 16, ... mỗi lần tăng kích thước phải copy mảng cũ sang mảng mới, tổng cộng nếu + thêm n ký tự (độ dài chuỗi sau cùng là n) thì thật ra sẽ tốn 3n phép gán. Gọi st.reserve(n+1) để đặt kích thước của mảng là n+1 (+1 cho ký tự '\0') thì sẽ bảo đảm mảng ko bị copy sang mảng mới, tốn còn n phép gán thay vì 3n.

còn tại sao là 3n thì gu gồ "amortized cost of dynamic table insertion" là biết...

thanks bạn nhiều :beauty:

Gửi bởi prog10

Bài này giải đúng thì O(logn), ko cần O(nlogn).

Thế theo bạn cần đổi thuật giải thế nào ?
hay là mỗi lần sau khi gán xâu mới mình kiểm tra xem cái số n đã xuất hiện trong xâu chưa ?, có thì in ra luôn không cần tính hết cả xâu ạ ?

**caohoangnam114** · 02-06-2014, 05:09 PM

Gửi bởi prog10

a/ Thực ra code này không chuẩn.
1. Để ý là có phép chia, đây là một phép tính rất tốn thời gian (chắc chắn là dịch thẳng từ Pascal, vì bước nhảy trong Pascal có giới hạn), ta có thể thay bằng phép cộng.
2. Nên ghi là j=i*i, và còn 1 chỗ không chuẩn nữa: phải là i<=sqrt((double)b, lúc này có thể đưa biểu thức căn ra khỏi vòng lặp, etc.
3. Thực ra sàng trong [a,b] ko cần sàng full, nhưng cứ cài sàng full cho chuẩn đã, khi đã hiểu thì mới qua sàng phân đoạn.

b/

Đối số là char* cơ mà [IMG]images/smilies/biggrin.png[/IMG]
std::string thì ko hề có khái niệm nhập có limit (có lẽ là ko cần đặt ra vấn đề buffer overrun với std::string?)

Tức là mình cần đổi thằng

Mã:

for (i=2; i<=b; i++)
    if (check[i])
      for (j=i; j<=b/i; j++) check[i*j]=0;

ra là

Mã:

for (i=2; i<=sqrt(b); i++)
    if (check[i])
      for (j=i*i; j<=sqrt(b); j++) check[i*j]=0;

như vậy à bác ?
cơ mà có cần thiết phải ép kiểu sang double không bác nhỉ ?, vì mình tưởng b kiểu long, sqrt(b) cũng là long thì i cũng vậy là hợp rồi chứ nhỉ ?