## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

// Program: string_matching.cpp // find the first occurrence of a fixed string within the // input text, and output the text so far #include #include // for std::noskipws int main (int argc, char* argv[]) { if (argc < 2) { // no command line arguments (except program name) std::cout << "Usage: string_matching2 \n"; return 1; } // search string: second command line argument const char* const s = argv[1]; // determine search string length m unsigned int m = 0; for (const char* p = s; *p != '\0'; ++p) ++m; // cyclic text window of size m char* const t = new char[m]; unsigned int w = 0; // number of characters read so far unsigned int i = 0; // index where t logically starts // find pattern in the text being read from std::cin std::cin >> std::noskipws; // don't skip whitespaces! for (unsigned int j = 0; j < m;) // compare search string with window at j-th element if (w < m || s[j] != t[(i+j)%m]) // input text still too short, or mismatch: // advance window by replacing first character if (std::cin >> t[i]) { std::cout << t[i]; ++w; // one more character read j = 0; // restart with first characters i = (i+1)%m; // of string and window } else break; // no more characters in the input else ++j; // match: go to next character std::cout << "\n"; delete[] t; return 0; }