String Algorithms(3,5,7)

- Basic Functions : strlen, substr, strcomp

- Argorithms

문자열 검색

- 정의 : 주어진 문자열 (haystack)에서 검색문자열(needle)을 모두 찾음.

- 알고리즘 KMP : 검색 중 needle 의 접미사와 접두사가 같은 부분이 있는 경우 지금까지 일치한 부분을 기준으로 비교하지 않아도 되는 곳을 건너띄고 비교하는 방식.

- 문제 유형 : 문자열 검색 및 접두사/접미사 관련 문제.

- 문제 : 접두사/접미사(NAMING), 펜린드롬 만들기(PALINDROMIZE), 재하의 금고(JAEHASAFE)

Suffix Array

- 정의 : 접미사 배열은 문자열을 각 S[..n] 으로 쪼갠 뒤 모든 접미사를 문자열의 알파벳 순으로 정렬한 것.

- 알고리즘 : manber myers

- 문제유형 : 사전 순서 관련된 문제로 동일한 부분문자열은 항상 인접한 접미사들의 접두사로 출현한다.

- 문제 : 원형 문자열(사전 가장 앞에), 서로 다른 부분 문자열의 수, 말버릇(HABIT)

Trie(ch26)

Graph

- 위상정렬, Euiler Circuit

- 고대어 사전, 낱말 끝말잇기

Dynamic Programming(ch08, ch09)

- OCR, MORSE, RESTORE

int mystrlen(const char *str){int n=0; for(;str[n]!='\0';n++); return n;}

void mysubstr(char* dst, const char* src, int begin, int end){

    int i=begin;

    for(;i<=end;i++){dst[i-begin] = src[i];}

    dst[end+1-begin] = '\0';

}

int mystrcmp(const char* str1, const char* str2){

    int i=0;

    while(str1[i]!='\0' && str2[i]!='\0'&& str1[i] == str2[i]){i++;}

    if(str1[i]!='\0' || str2[i] !='\0'){ return str1[i] < str2[i]?-1:1;}

    if(str1[i]=='\0' && str2[i]=='\0'){return 0;}

}

#include <stdio.h>

int index[100];

size_t strlen(const char* str){

size_t n=0;

while(str[n]!='\0'){

n++;

}

return n;

}

//find H N

void naiveSearch(const char* H, const char* N){

for(int i=0;i<100;i++){

index[i] = -1;

}

size_t hN = strlen(H);

size_t nN = strlen(N);

int indexI=0;

for(unsigned int i=0;i<hN-nN;i++){

bool same = true;

for(unsigned int j=0;j<nN;j++){

if(H[i+j]!=N[j]){

same =false;

break;

}

}

if(same){

index[indexI]=i;

indexI++;

}

}

}

void main(){

naiveSearch("avadakedavra","aked");

for(int i=0;i<100 && index[i]>-1;i++){

printf("%d

",index[i]);

}

}

original url: http://stackoverflow.com/questions/6010864/why-copying-stringstream-is-not-allowed

Copying of ANY stream in C++ is disabled by having made the copy constructor private.

Any means ANY, whether it is stringstream, istream, ostream,iostream or whatever.

Copying of stream is disabled because it doesn't make sense. Its very very very important to understand what stream means, to actually understand why copying stream does not make sense. stream is not a container that you can make copy of. It doesn't contain data.

If a list/vector/map or any container is a bucket, then stream is a hose through which data flows. Think of stream as some pipe through which you get data; a pipe - at one side is the source (sender), on the other side is the sink (receiver). That is called unidirectional stream. There're also bidirectional streams through which data flows in both direction. So what does it make sense making a copy of such a thing? It doesn't contain any data at all. It is through which you get data.

Now suppose for a while if making a copy of stream is allowed, and you created a copy of std::cin which is in fact input stream. Say the copied object is copy_cin. Now ask yourself : does it make sense to read data from copy_cin stream when the very same data has already been read from std::cin. No, it doesn't make sense, because the user entered the data only once, the keyboard (or the input device) generated the electric signals only once and they flowed through all other hardwares and low-level APIs only once. How can your program read it twice or more?

Hence, creating copy is not allowed, but creating reference is allowed:

std::istream copy_cin = std::cin; //error

std::istream & ref_cin = std::cin; //ok

Also note that you can create another instance of stream and can make it use the same underlying buffer which the old stream is currently using. See this : https://ideone.com/rijov