iframe-proxy | Sunbelt Computer Software

66 lines (62 loc) · 1.52 KB

#include <iostream>
#include <string>
#include <vector>
 * Function to fill in zvalues vector of ztext
std::vector<size_t> fillZvalues(const std::string & ztext) {
	size_t n = ztext.length();
	std::vector<size_t> zvals(n, 0);
	size_t L = 0, R = 0; 								// s[L..R] represent the prefix string.
	for (size_t i = 1; i < n; ++i) {
		if ( i > R ) {
			L = R = i;
			while( R < n && ztext[R-L] == ztext[R] ) {
			zvals[i] = R-L;
			size_t K = i - L;
			if( zvals[K] < R-i+1 ) {
				zvals[i] = zvals[K];
			} else {
				L = R = i;
				while( R < n && ztext[R-L] == ztext[R] ) {
				zvals[i] = R-L;
	return zvals;
 * This function returns index of text where pattern matches using z algorithm
std::vector<size_t> search( const std::string & text, const std::string & pattern ) {
	std::string ztext = pattern + '$' + text;
	std::vector<size_t> zvalues = fillZvalues(ztext);
	std::vector<size_t> indices;
	for ( size_t i = 1; i < zvalues.size(); ++i ) {
		if (zvalues[i] == pattern.length()) {
			indices.push_back(i - pattern.length() -1 );
	return indices;
	std::string text, pattern;
	std::cout << "String searching using Z algorithm:\n";
	std::cout << "Enter text:";
	std::getline(std::cin, text);
	std::cout << "Pattern :";
	std::getline(std::cin, pattern);
	std::vector<size_t> indices = search(text, pattern);
	for (auto i : indices ) {
		std::cout << pattern << " occurs in given text starting at index " << i << std::endl;

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

z.cpp

Latest commit

History

z.cpp

File metadata and controls