[Exercises 1]
/*
Write a function String::Frequency that determines the frequency of occurence of each of the distinct characters in the string.
문자열의 알파벳들의 출현빈도를 가늠하는 String::Frequency 함수를 작성한다.
*/
#include <iostream>
using namespace std;
class String
{
private:
char *str;
int len;
int *f; //실패 함수용
public:
String(char *init, int m) :len(m)
{
str = new char[m + 1];
f = new int[m];
for (int i = 0; i < m; i++)
{
str[i] = init[i];
}
str[m] = '\0'; //문자열의 끝은 항상 널이다
FailureFunction();
}
~String()
{
if (str != NULL)
{
delete[]str;
str = NULL;
}
if (f != NULL)
{
delete[]f;
f = NULL;
}
}
String(const String &t) :len(t.len)
{
str = new char[t.len + 1];
f = new int[t.len];
for (int i = 0; i < len; i++)
{
str[i] = t.str[i];
}
str[len] = '\0';
FailureFunction();
}
bool operator==(String t)
{
if (len != t.len)
return false;
else
{
for (int i = 0; i < len; i++)
{
if (str[i] != t.str[i]) //하나라도 다르면
return false;
}
}
return true;
}
bool operator!() //문자열이 존재하지 않을 때 참
{
if (len != 0)
return false;
else if (str[0] != '\0')
return false;
else
return true;
}
int Length()
{
return len;
}
String Concat(String t) //문자열을 합친다 C언어의 strcat
{
char *s = new char[Length() + t.Length() + 1];
int idx = 0;
for (int i = 0; i < Length(); i++)
{
s[idx++] = str[i];
}
for (int i = 0; i < t.Length(); i++)
{
s[idx++] = t.str[i];
}
s[idx] = '\0'; //문자열의 끝
String copy(s, idx); //동적할당 메모리 반환 위해
delete[]s;
s = NULL;
return copy;
}
String SubStr(int i, int j)
{
char *subStr = new char[j + 1];
int idx = 0;
for (int k = i; k < i + j; k++)
subStr[idx++] = str[k]; //문자열의 일부분
subStr[idx] = '\0';
String copy(subStr, idx);
delete[]subStr;
subStr = NULL;
return copy;
}
int Find(String pat)
{ // If pat is found in *this, then return start position of pat in *this
// Otherwise, return -1
for (int start = 0; start <= Length() - pat.Length(); start++)
{ // Check pattern match at str[start]
int j;
for (j = 0; (j < pat.Length()) && (str[start + j] == pat.str[j]); j++);
if (j == pat.Length())
return start; // Found match
}
return -1; // pat is empty or not exist in *this
}
int FastFind(String pat) //Program 2.16, Knuth-Morrs-Pratt 알고리즘
{
int posP = 0, posS = 0;
int lengthP = pat.Length(), lengthS = Length();
while ((posP < lengthP) && (posS < lengthS))
if (pat.str[posP] == str[posS]) //문자 일치한다면
{
posP++;
posS++;
}
else
{
if (posP == 0) //문자가 일치하지 않고 posP가 0이라면
posS++;
else //문자가 일치하지 않고 posP가 0이 아니라면
posP = pat.f[posP - 1] + 1;
}
if (posP < lengthP)
return -1;
else
return posS - lengthP;
}
void FailureFunction() //Program 2.17
{
//실패 함수 계산
int lengthP = Length();
f[0] = -1;
for (int j = 1; j < lengthP; j++)
{
int i = f[j - 1];
while ((*(str + j) != *(str + i + 1)) && (i >= 0))
i = f[i];
if (*(str + j) == *(str + i + 1))
f[j] = i + 1;
else
f[j] = -1;
}
}
void Frequency()
{
int alphabet[26] = { 0, };
for (int i = 0; i < Length(); i++)
{
if (str[i] >= 'a'&&str[i] <= 'z')
{
alphabet[str[i] - 97]++; //아스키 코드 값대로 a=97
}
else if (str[i] >= 'A'&&str[i] <= 'Z')
{
alphabet[str[i] - 65]++; //A=65
}
}
cout << "문자열: " << str << "의 문자 빈도수" << endl;
for (int i = 0; i < 26; i++)
{
if (alphabet[i] != 0)
{
cout << (char)(i + 65) << "(" << (char)(i + 97) << "): " << alphabet[i] << endl;
}
}
}
friend ostream &operator<<(ostream &os, const String &t);
};
ostream &operator<<(ostream &os, const String &t)
{
os << t.str << endl;
return os;
}
int main(void)
{
String str("Gudetama", 9);
cout << "문자열: " << str << endl;
str.Frequency();
return 0;
}
[Exercises 2]
/*
Write a fucntion, String::Delete, that accepts two integers, start and length.
start와 length 두개의 인자를 전달 받는 String::Delete 함수를 작성한다.
The function computes a new string that is equivalent to the original string, except that length characters beginning at start have been removed
이 함수는 기존함수와 동일한 문자열을 복사하지만, start부터 length만큼의 문자는 지운채로 복사한다
*/
#include <iostream>
using namespace std;
class String
{
private:
char *str;
int len;
int *f; //실패 함수용
public:
String(char *init, int m) :len(m)
{
str = new char[m + 1];
f = new int[m];
for (int i = 0; i < m; i++)
{
str[i] = init[i];
}
str[m] = '\0'; //문자열의 끝은 항상 널이다
FailureFunction();
}
~String()
{
if (str != NULL)
{
delete[]str;
str = NULL;
}
if (f != NULL)
{
delete[]f;
f = NULL;
}
}
String(const String &t) :len(t.len)
{
str = new char[t.len + 1];
f = new int[t.len];
for (int i = 0; i < len; i++)
{
str[i] = t.str[i];
}
str[len] = '\0';
FailureFunction();
}
bool operator==(String t)
{
if (len != t.len)
return false;
else
{
for (int i = 0; i < len; i++)
{
if (str[i] != t.str[i]) //하나라도 다르면
return false;
}
}
return true;
}
bool operator!() //문자열이 존재하지 않을 때 참
{
if (len != 0)
return false;
else if (str[0] != '\0')
return false;
else
return true;
}
int Length()
{
return len;
}
String Concat(String t) //문자열을 합친다 C언어의 strcat
{
char *s = new char[Length() + t.Length() + 1];
int idx = 0;
for (int i = 0; i < Length(); i++)
{
s[idx++] = str[i];
}
for (int i = 0; i < t.Length(); i++)
{
s[idx++] = t.str[i];
}
s[idx] = '\0'; //문자열의 끝
String copy(s, idx); //동적할당 메모리 반환 위해
delete[]s;
s = NULL;
return copy;
}
String SubStr(int i, int j)
{
char *subStr = new char[j + 1];
int idx = 0;
for (int k = i; k < i + j; k++)
subStr[idx++] = str[k]; //문자열의 일부분
subStr[idx] = '\0';
String copy(subStr, idx);
delete[]subStr;
subStr = NULL;
return copy;
}
int Find(String pat)
{ // If pat is found in *this, then return start position of pat in *this
// Otherwise, return -1
for (int start = 0; start <= Length() - pat.Length(); start++)
{ // Check pattern match at str[start]
int j;
for (j = 0; (j < pat.Length()) && (str[start + j] == pat.str[j]); j++);
if (j == pat.Length())
return start; // Found match
}
return -1; // pat is empty or not exist in *this
}
int FastFind(String pat) //Program 2.16, Knuth-Morrs-Pratt 알고리즘
{
int posP = 0, posS = 0;
int lengthP = pat.Length(), lengthS = Length();
while ((posP < lengthP) && (posS < lengthS))
if (pat.str[posP] == str[posS]) //문자 일치한다면
{
posP++;
posS++;
}
else
{
if (posP == 0) //문자가 일치하지 않고 posP가 0이라면
posS++;
else //문자가 일치하지 않고 posP가 0이 아니라면
posP = pat.f[posP - 1] + 1;
}
if (posP < lengthP)
return -1;
else
return posS - lengthP;
}
void FailureFunction() //Program 2.17
{
//실패 함수 계산
int lengthP = Length();
f[0] = -1;
for (int j = 1; j < lengthP; j++)
{
int i = f[j - 1];
while ((*(str + j) != *(str + i + 1)) && (i >= 0))
i = f[i];
if (*(str + j) == *(str + i + 1))
f[j] = i + 1;
else
f[j] = -1;
}
}
void Frequency()
{
int alphabet[26] = { 0, };
for (int i = 0; i < Length(); i++)
{
if (str[i] >= 'a'&&str[i] <= 'z')
{
alphabet[str[i] - 97]++; //아스키 코드 값대로 a=97
}
else if (str[i] >= 'A'&&str[i] <= 'Z')
{
alphabet[str[i] - 65]++; //A=65
}
}
cout << "문자열: " << str << "의 문자 빈도수" << endl;
for (int i = 0; i < 26; i++)
{
if (alphabet[i] != 0)
{
cout << (char)(i + 65) << "(" << (char)(i + 97) << "): " << alphabet[i] << endl;
}
}
}
String Delete(int start, int length)
{
char *t = new char[Length() + 1];
int idx = 0;
for (int i = 0; i < Length(); i++)
{
if (i >= start&&i < start + length) //start 이후는 복사하지 않는다
continue;
else
t[idx++] = str[i];
}
t[idx] = '\0';
String copy(t, idx);
delete[]t;
t = NULL; //동적할당한 메모리 반환 위해
return copy;
}
friend ostream &operator<<(ostream &os, const String &t);
};
ostream &operator<<(ostream &os, const String &t)
{
os << t.str << endl;
return os;
}
int main(void)
{
String str("Gudetama", 9);
cout << "문자열: " << str << endl;
String del = str.Delete(3, 2); //Gudama 즉, str[3] 과 str[4]가 지워진 것이다
cout << del;
return 0;
}
[Exercises 3]
/*
Write a function, String:::CharDelete, that accepts a character c.
문자 c를 인자로 전달받는 String::CharDelete 함수를 작성한다.
The function returns the string with all occurences of c removed.
이 함수가 실행되면 문자열에서 c 문자는 전부 제거된다
*/
#include <iostream>
using namespace std;
class String
{
private:
char *str;
int len;
int *f; //실패 함수용
public:
String(char *init, int m) :len(m)
{
str = new char[m + 1];
f = new int[m];
for (int i = 0; i < m; i++)
{
str[i] = init[i];
}
str[m] = '\0'; //문자열의 끝은 항상 널이다
FailureFunction();
}
~String()
{
if (str != NULL)
{
delete[]str;
str = NULL;
}
if (f != NULL)
{
delete[]f;
f = NULL;
}
}
String(const String &t) :len(t.len)
{
str = new char[t.len + 1];
f = new int[t.len];
for (int i = 0; i < len; i++)
{
str[i] = t.str[i];
}
str[len] = '\0';
FailureFunction();
}
bool operator==(String t)
{
if (len != t.len)
return false;
else
{
for (int i = 0; i < len; i++)
{
if (str[i] != t.str[i]) //하나라도 다르면
return false;
}
}
return true;
}
bool operator!() //문자열이 존재하지 않을 때 참
{
if (len != 0)
return false;
else if (str[0] != '\0')
return false;
else
return true;
}
int Length()
{
return len;
}
String Concat(String t) //문자열을 합친다 C언어의 strcat
{
char *s = new char[Length() + t.Length() + 1];
int idx = 0;
for (int i = 0; i < Length(); i++)
{
s[idx++] = str[i];
}
for (int i = 0; i < t.Length(); i++)
{
s[idx++] = t.str[i];
}
s[idx] = '\0'; //문자열의 끝
String copy(s, idx); //동적할당 메모리 반환 위해
delete[]s;
s = NULL;
return copy;
}
String SubStr(int i, int j)
{
char *subStr = new char[j + 1];
int idx = 0;
for (int k = i; k < i + j; k++)
subStr[idx++] = str[k]; //문자열의 일부분
subStr[idx] = '\0';
String copy(subStr, idx);
delete[]subStr;
subStr = NULL;
return copy;
}
int Find(String pat)
{ // If pat is found in *this, then return start position of pat in *this
// Otherwise, return -1
for (int start = 0; start <= Length() - pat.Length(); start++)
{ // Check pattern match at str[start]
int j;
for (j = 0; (j < pat.Length()) && (str[start + j] == pat.str[j]); j++);
if (j == pat.Length())
return start; // Found match
}
return -1; // pat is empty or not exist in *this
}
int FastFind(String pat) //Program 2.16, Knuth-Morrs-Pratt 알고리즘
{
int posP = 0, posS = 0;
int lengthP = pat.Length(), lengthS = Length();
while ((posP < lengthP) && (posS < lengthS))
if (pat.str[posP] == str[posS]) //문자 일치한다면
{
posP++;
posS++;
}
else
{
if (posP == 0) //문자가 일치하지 않고 posP가 0이라면
posS++;
else //문자가 일치하지 않고 posP가 0이 아니라면
posP = pat.f[posP - 1] + 1;
}
if (posP < lengthP)
return -1;
else
return posS - lengthP;
}
void FailureFunction() //Program 2.17
{
//실패 함수 계산
int lengthP = Length();
f[0] = -1;
for (int j = 1; j < lengthP; j++)
{
int i = f[j - 1];
while ((*(str + j) != *(str + i + 1)) && (i >= 0))
i = f[i];
if (*(str + j) == *(str + i + 1))
f[j] = i + 1;
else
f[j] = -1;
}
}
void Frequency()
{
int alphabet[26] = { 0, };
for (int i = 0; i < Length(); i++)
{
if (str[i] >= 'a'&&str[i] <= 'z')
{
alphabet[str[i] - 97]++; //아스키 코드 값대로 a=97
}
else if (str[i] >= 'A'&&str[i] <= 'Z')
{
alphabet[str[i] - 65]++; //A=65
}
}
cout << "문자열: " << str << "의 문자 빈도수" << endl;
for (int i = 0; i < 26; i++)
{
if (alphabet[i] != 0)
{
cout << (char)(i + 65) << "(" << (char)(i + 97) << "): " << alphabet[i] << endl;
}
}
}
String Delete(int start, int length)
{
char *t = new char[Length() + 1];
int idx = 0;
for (int i = 0; i < Length(); i++)
{
if (i >= start&&i < start + length) //start 이후는 복사하지 않는다
continue;
else
t[idx++] = str[i];
}
t[idx] = '\0';
String copy(t, idx);
delete[]t;
t = NULL; //동적할당한 메모리 반환 위해
return copy;
}
String CharDelete(char c)
{
char *t = new char[Length() + 1];
int idx = 0;
for (int i = 0; i < Length(); i++)
{
if (c == str[i]) //문자 c는 제거되어야한다
continue;
else
t[idx++] = str[i];
}
t[idx] = '\0';
String copy(t, idx);
delete[]t;
t = NULL; //동적할당한 메모리 반환 위해
cout << "문자 " << c << "를 지웁니다" << endl;
return copy;
}
friend ostream &operator<<(ostream &os, const String &t);
};
ostream &operator<<(ostream &os, const String &t)
{
os << t.str << endl;
return os;
}
int main(void)
{
String str("Gudetama", 9);
cout << "문자열: " << str << endl;
String del = str.CharDelete('a'); //Gudetm
cout << del;
return 0;
}
[Exercises 4]
/*
Write a function to make an inplace replacement of a substring w of a string by the string x.
문자열의 일부 w를 문자열 x로 대체하는 함수를 작성한다.
Note that w may not be of the same size as x
x와 w의 길이는 동일하지 않을 수 있다
*/
#include <iostream>
using namespace std;
class String
{
private:
char *str;
int len;
int *f; //실패 함수용
public:
String(char *init, int m) :len(m)
{
str = new char[m + 1];
f = new int[m];
for (int i = 0; i < m; i++)
{
str[i] = init[i];
}
str[m] = '\0'; //문자열의 끝은 항상 널이다
FailureFunction();
}
~String()
{
if (str != NULL)
{
delete[]str;
str = NULL;
}
if (f != NULL)
{
delete[]f;
f = NULL;
}
}
String(const String &t) :len(t.len)
{
str = new char[t.len + 1];
f = new int[t.len];
for (int i = 0; i < len; i++)
{
str[i] = t.str[i];
}
str[len] = '\0';
FailureFunction();
}
bool operator==(String t)
{
if (len != t.len)
return false;
else
{
for (int i = 0; i < len; i++)
{
if (str[i] != t.str[i]) //하나라도 다르면
return false;
}
}
return true;
}
bool operator!() //문자열이 존재하지 않을 때 참
{
if (len != 0)
return false;
else if (str[0] != '\0')
return false;
else
return true;
}
int Length()
{
return len;
}
String Concat(String t) //문자열을 합친다 C언어의 strcat
{
char *s = new char[Length() + t.Length() + 1];
int idx = 0;
for (int i = 0; i < Length(); i++)
{
s[idx++] = str[i];
}
for (int i = 0; i < t.Length(); i++)
{
s[idx++] = t.str[i];
}
s[idx] = '\0'; //문자열의 끝
String copy(s, idx); //동적할당 메모리 반환 위해
delete[]s;
s = NULL;
return copy;
}
String SubStr(int i, int j)
{
char *subStr = new char[j + 1];
int idx = 0;
for (int k = i; k < i + j; k++)
subStr[idx++] = str[k]; //문자열의 일부분
subStr[idx] = '\0';
String copy(subStr, idx);
delete[]subStr;
subStr = NULL;
return copy;
}
int Find(String pat)
{ // If pat is found in *this, then return start position of pat in *this
// Otherwise, return -1
for (int start = 0; start <= Length() - pat.Length(); start++)
{ // Check pattern match at str[start]
int j;
for (j = 0; (j < pat.Length()) && (str[start + j] == pat.str[j]); j++);
if (j == pat.Length())
return start; // Found match
}
return -1; // pat is empty or not exist in *this
}
int FastFind(String pat) //Program 2.16, Knuth-Morrs-Pratt 알고리즘
{
int posP = 0, posS = 0;
int lengthP = pat.Length(), lengthS = Length();
while ((posP < lengthP) && (posS < lengthS))
if (pat.str[posP] == str[posS]) //문자 일치한다면
{
posP++;
posS++;
}
else
{
if (posP == 0) //문자가 일치하지 않고 posP가 0이라면
posS++;
else //문자가 일치하지 않고 posP가 0이 아니라면
posP = pat.f[posP - 1] + 1;
}
if (posP < lengthP)
return -1;
else
return posS - lengthP;
}
void FailureFunction() //Program 2.17
{
//실패 함수 계산
int lengthP = Length();
f[0] = -1;
for (int j = 1; j < lengthP; j++)
{
int i = f[j - 1];
while ((*(str + j) != *(str + i + 1)) && (i >= 0))
i = f[i];
if (*(str + j) == *(str + i + 1))
f[j] = i + 1;
else
f[j] = -1;
}
}
void Frequency()
{
int alphabet[26] = { 0, };
for (int i = 0; i < Length(); i++)
{
if (str[i] >= 'a'&&str[i] <= 'z')
{
alphabet[str[i] - 97]++; //아스키 코드 값대로 a=97
}
else if (str[i] >= 'A'&&str[i] <= 'Z')
{
alphabet[str[i] - 65]++; //A=65
}
}
cout << "문자열: " << str << "의 문자 빈도수" << endl;
for (int i = 0; i < 26; i++)
{
if (alphabet[i] != 0)
{
cout << (char)(i + 65) << "(" << (char)(i + 97) << "): " << alphabet[i] << endl;
}
}
}
String Delete(int start, int length)
{
char *t = new char[Length() + 1];
int idx = 0;
for (int i = 0; i < Length(); i++)
{
if (i >= start&&i < start + length) //start 이후는 복사하지 않는다
continue;
else
t[idx++] = str[i];
}
t[idx] = '\0';
String copy(t, idx);
delete[]t;
t = NULL; //동적할당한 메모리 반환 위해
return copy;
}
String CharDelete(char c)
{
char *t = new char[Length() + 1];
int idx = 0;
for (int i = 0; i < Length(); i++)
{
if (c == str[i]) //문자 c는 제거되어야한다
continue;
else
t[idx++] = str[i];
}
t[idx] = '\0';
String copy(t, idx);
delete[]t;
t = NULL; //동적할당한 메모리 반환 위해
cout << "문자 " << c << "를 지웁니다" << endl;
return copy;
}
String Replace(String w, String x)
{
int start = Find(w);
cout << "문자열 " << w << "를 문자열 " << x << "로 대체합니다" << endl;
String copy = SubStr(0, start);
String copy2 = copy.Concat(x);
String copy3 = SubStr(start + w.Length(), Length());
String result = copy2.Concat(copy3);
return result;
}
friend ostream &operator<<(ostream &os, const String &t);
};
ostream &operator<<(ostream &os, const String &t)
{
os << t.str;
return os;
}
int main(void)
{
String str("Gudetama", 8);
String w("det", 3);
String x("ted", 3);
cout << "문자열: " << str << endl;
String del = str.Replace(w, x);
cout << del << endl;
return 0;
}
[Exercises 5]
/*
If x=(x(0),...x(m-1)) and y=(y(0),...,y(n-1)) are strings, where x(i) and y(i) are letters of the alphabet
x=(x(0),...x(m-1)) 와 y=(y(0),...,y(n-1))가 알파벳으로 이루어진 문자열들이라면,
then x is less than y if x(i)=y(i) for 0<=i<j and x(j)<y(j) or if x(i)=y(i) for 0<=i<=m and m<n.
i가 0과 j 사이이고 x(i)=y(i)이면 x가 y보다 작고, i가 0과 m 사이이고 m이 n보다 작은 상태에서 x(i)=y(i)이면 x가 y보다 작다.
Write an algorithm that takes two strings x, y and returns either -1, 0, or +1 if x<y, x=y, x>y respectively.
두개의 문자열 x, y를 비교했을 때 x<y이면 -1 x=y이면 1 x>y이면 1을 반환하는 알고리즘을 작성한다
*/
#include <iostream>
using namespace std;
class String
{
private:
char *str;
int len;
int *f; //실패 함수용
public:
String(char *init, int m) :len(m)
{
str = new char[m + 1];
f = new int[m];
for (int i = 0; i < m; i++)
{
str[i] = init[i];
}
str[m] = '\0'; //문자열의 끝은 항상 널이다
FailureFunction();
}
~String()
{
if (str != NULL)
{
delete[]str;
str = NULL;
}
if (f != NULL)
{
delete[]f;
f = NULL;
}
}
String(const String &t) :len(t.len)
{
str = new char[t.len + 1];
f = new int[t.len];
for (int i = 0; i < len; i++)
{
str[i] = t.str[i];
}
str[len] = '\0';
FailureFunction();
}
bool operator==(String t)
{
if (len != t.len)
return false;
else
{
for (int i = 0; i < len; i++)
{
if (str[i] != t.str[i]) //하나라도 다르면
return false;
}
}
return true;
}
bool operator!() //문자열이 존재하지 않을 때 참
{
if (len != 0)
return false;
else if (str[0] != '\0')
return false;
else
return true;
}
int Length()
{
return len;
}
String Concat(String t) //문자열을 합친다 C언어의 strcat
{
char *s = new char[Length() + t.Length() + 1];
int idx = 0;
for (int i = 0; i < Length(); i++)
{
s[idx++] = str[i];
}
for (int i = 0; i < t.Length(); i++)
{
s[idx++] = t.str[i];
}
s[idx] = '\0'; //문자열의 끝
String copy(s, idx); //동적할당 메모리 반환 위해
delete[]s;
s = NULL;
return copy;
}
String SubStr(int i, int j)
{
char *subStr = new char[j + 1];
int idx = 0;
for (int k = i; k < i + j; k++)
subStr[idx++] = str[k]; //문자열의 일부분
subStr[idx] = '\0';
String copy(subStr, idx);
delete[]subStr;
subStr = NULL;
return copy;
}
int Find(String pat)
{ // If pat is found in *this, then return start position of pat in *this
// Otherwise, return -1
for (int start = 0; start <= Length() - pat.Length(); start++)
{ // Check pattern match at str[start]
int j;
for (j = 0; (j < pat.Length()) && (str[start + j] == pat.str[j]); j++);
if (j == pat.Length())
return start; // Found match
}
return -1; // pat is empty or not exist in *this
}
int FastFind(String pat) //Program 2.16, Knuth-Morrs-Pratt 알고리즘
{
int posP = 0, posS = 0;
int lengthP = pat.Length(), lengthS = Length();
while ((posP < lengthP) && (posS < lengthS))
if (pat.str[posP] == str[posS]) //문자 일치한다면
{
posP++;
posS++;
}
else
{
if (posP == 0) //문자가 일치하지 않고 posP가 0이라면
posS++;
else //문자가 일치하지 않고 posP가 0이 아니라면
posP = pat.f[posP - 1] + 1;
}
if (posP < lengthP)
return -1;
else
return posS - lengthP;
}
void FailureFunction() //Program 2.17
{
//실패 함수 계산
int lengthP = Length();
f[0] = -1;
for (int j = 1; j < lengthP; j++)
{
int i = f[j - 1];
while ((*(str + j) != *(str + i + 1)) && (i >= 0))
i = f[i];
if (*(str + j) == *(str + i + 1))
f[j] = i + 1;
else
f[j] = -1;
}
}
void Frequency()
{
int alphabet[26] = { 0, };
for (int i = 0; i < Length(); i++)
{
if (str[i] >= 'a'&&str[i] <= 'z')
{
alphabet[str[i] - 97]++; //아스키 코드 값대로 a=97
}
else if (str[i] >= 'A'&&str[i] <= 'Z')
{
alphabet[str[i] - 65]++; //A=65
}
}
cout << "문자열: " << str << "의 문자 빈도수" << endl;
for (int i = 0; i < 26; i++)
{
if (alphabet[i] != 0)
{
cout << (char)(i + 65) << "(" << (char)(i + 97) << "): " << alphabet[i] << endl;
}
}
}
String Delete(int start, int length)
{
char *t = new char[Length() + 1];
int idx = 0;
for (int i = 0; i < Length(); i++)
{
if (i >= start&&i < start + length) //start 이후는 복사하지 않는다
continue;
else
t[idx++] = str[i];
}
t[idx] = '\0';
String copy(t, idx);
delete[]t;
t = NULL; //동적할당한 메모리 반환 위해
return copy;
}
String CharDelete(char c)
{
char *t = new char[Length() + 1];
int idx = 0;
for (int i = 0; i < Length(); i++)
{
if (c == str[i]) //문자 c는 제거되어야한다
continue;
else
t[idx++] = str[i];
}
t[idx] = '\0';
String copy(t, idx);
delete[]t;
t = NULL; //동적할당한 메모리 반환 위해
cout << "문자 " << c << "를 지웁니다" << endl;
return copy;
}
String Replace(String w, String x)
{
int start = Find(w);
cout << "문자열 " << w << "를 문자열 " << x << "로 대체합니다" << endl;
String copy = SubStr(0, start);
String copy2 = copy.Concat(x);
String copy3 = SubStr(start + w.Length(), Length());
String result = copy2.Concat(copy3);
return result;
}
friend int Compare(String &s, String &t);
friend ostream &operator<<(ostream &os, const String &t);
};
int Compare(String &s, String &t)
{
char *copy = new char[s.Length() + 1];
char *copy2 = new char[s.Length() + 1];
for (int i = 0; i < s.Length(); i++)
copy[i] = s.str[i];
for (int i = 0; i < t.Length(); i++)
copy2[i] = t.str[i];
if (s.Length() < t.Length())
return -1;
else if (s.Length() == t.Length())
{
int equal = 0;
for (int i = 0; i < s.Length(); i++)
{
if (copy[i] != copy2[i] && copy[i] > copy2[i])
{
equal++;
break;
}
else if (copy[i] != copy2[i] && copy[i] < copy2[i])
{
equal--;
break;
}
}
if (equal == 0)
return 0;
else if (equal > 0)
return 1;
else
return -1;
}
else
return 1;
}
ostream &operator<<(ostream &os, const String &t)
{
os << t.str;
return os;
}
int main(void)
{
String str("Gudetama", 8);
String str2("Gudetamama", 10);
int result = Compare(str, str2);
if (result > 0)
cout << str << "이 " << str2 << "보다 크다" << endl;
else if (result == 0)
cout << str << "과 " << str2 << "는 동일한 문자열이다" << endl;
else
cout << str2 << "이 " << str << "보다 크다" << endl;
return 0;
}
[Exercises 7]
/*
Compute the failure function for each of the following patterns:
다음의 패턴마다 실패 함수를 작성해라
*/
(a)
a a a a b
-1 0 1 2 -1
(b)
a b a b a a
-1 -1 0 1 2 0
(c)
a b a a b a a b b
-1 -1 0 0 1 2 3 4 -1
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서,
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*6, 8, 9번 문제는 프로그래밍 문제가 아니기 때문에 생략했습니다.
*7번 문제는 책과 함께 https://m.blog.naver.com/PostView.nhn?blogId=tpinlab&logNo=10119424299&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F 여기를 참고했습니다
'C++ > Fundamentals of Data Structures in C++(Horowitz)' 카테고리의 다른 글
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.8 연습문제 5~9 (0) | 2017.08.04 |
|---|---|
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.8 연습문제 1~4 (0) | 2017.08.03 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.5 연습문제 (0) | 2017.07.31 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.4 연습문제 (0) | 2017.07.29 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.3 연습문제 7~9 (0) | 2017.07.28 |