Program 2 – Detecting Substrings (C++ Version)
Introduction
A very common task that is often performed by programs that work with text files is the problem of locating a specific substring within the file. I am sure we’ve all done this many times when working with Word, Notepad, or other editors.
Since we don’t have a GUI or other means of displaying the contents of a file all at once, let’s modify the problem slightly. Rather than locating a specific substring within a file and then highlighting the results, as most modern programs would do, let’s write a C++ program that locates the occurrences of a specific substring within a file and then displays the occurrence number as well as a portion of the text around the found substring. It should also count the number of occurrences and indicate that number in a brief report at the end.
CS1337 – Computer Science I page: 5
The input file that we will use for this exercise is a text copy of the Declaration of Independence. You will find this in the input file “DeclOfIndep.txt” on eLearning. It is okay to hard code this file name for this project, but in the future, you might have your program ask the user for the filename. That would generalize your program to work on any input file.
Even though this is a C++ program, let’s use C-strings in this exercise for all string operations. Thus, your program will read each line of input from the file into a C-string, not into a C++ string. The functions you use to locate the substrings should be C-string functions and not members of the string class. All printing and other manipulations on strings should be done with C-strings. In short, there should be no C++ strings used in this program. (Therefore, do not #include .)
Overview
Here’s a high-level overview of what your program should do:
1) Ask the user for the substring to search for (and store it in a C-string). 2) Calculate and display each of the found occurrences of the substring in the file. For each found occurrence, your program should display (a) the location number starting at 1 and going up to the total number of locations found, and (b) the portion of the string containing the found substring. This portion should consist of the substring itself and up to 8 characters before and 8 characters after the found substring. (Note that if the substring is within 8 characters of the end of a line this won’t be possible.)
Sample Runs
Here is a sample run looking for the string “people” in the file “DeclOfIndep.txt”.
Looking for the substring "people" in file "DeclOfIndep.txt":
Location 1: String: "for one people to" Location 2: String: "icts of people, unless" Location 3: String: "s those people would r" Location 4: String: " of the people." Location 5: String: " of our people."
There were 5 occurrences of the string "people" within the file "DeclOfIndep.txt".
Or consider another run looking for the substring “oo” in the file “DeclOfIndep.txt.”
Looking for the substring "oo" in file "DeclOfIndep.txt":
Location 1: String: "public goooood." Location 2: String: "ublic goooood."
CS1337 – Computer Science I page: 6
Location 3: String: "blic goooood." Location 4: String: "lic goooood." Location 5: String: "armed troops among" Location 6: String: ". They too have" Location 7: String: "of the good People" Location 8: String: "illiam Hooper" Location 9: String: "s Lightfoot Lee" Location 10: String: "Witherspoon"
There were 10 occurrences of the string "oo" within the file "DeclOfIndep.txt".
Programming Notes:
There are several points to be made about this problem in general, and about both sample runs.
1) Both of the sample runs given above are actual data, so you can use them to test your program.
2) Note that we deliberately modified a single word “good” in the Declaration file to “goooood”. In other words, we added some extra “o’s” to the word.
This makes the point that some substrings can overlap. For example, if we search for “oo” in the word “goooood,” the first “oo” will certainly be a hit. But the second hit occurs with the second “o” of the first hit, i.e., the two instances of “oo” overlap. Because of this overlap, there are really four hits of “oo” within that word, as illustrated above, not two, and your program should find all four of them.
3) Do not use “inFile >>” to read the data from the input file. As you know, “inFile >>” tokenizes around white space and would therefore extract each word from the input file separately. Of course, this has both advantages and disadvantages depending on the circumstances. It would, for example, be a good function to use if we wanted to process within individual words only. But since our program should be able to detect substrings consisting of more than one word, “inFile >>” will not serve our purposes.
Therefore, use “inFile.getline()” (i.e., the member function version of getline() – see Chapter 10, Slide 17+.) as your primary input function. As we discussed in class, this will read a single line of input from the file at a time and place it in the target buffer, which should be a character array of adequate size.
4) Note that the file will be processed one line at a time. It is not necessary to look for substrings that span more than one line.
5) Since we are using C-strings for this assignment, we’ll have to use the C string processing functions. A very useful function for this assignment would be the strstr(const char *, const char *) function, which locates an instance of
CS1337 – Computer Science I page: 7
the right hand string inside the left hand string and returns a pointer to the found instance. (It returns a NULL if no instance is found.) This function is described on slide 27 of the Chapter 10 slide set. The strchr(const char *, int ch), not listed in the slide set, locates the first occurrence of “ch” in the string and returns a pointer to it.
6) Since all C-strings are based on character arrays, be careful about running off either end of the array. Since you are required to print not only the substring but also 8 characters to either side of it, this overrun can occur if the substring you are looking for is within 8 characters of either the beginning or the end of that line. (Often an array overrun will be detected if your program starts printing out gibberish or default characters instead of text from the Declaration.)
For an example, consider the first sample run (i.e., looking for the word “people”). Note that in locations 4 and 5, the word “people” appears not only at the end of a sentence but also at the end of a line of input. It is, therefore, impossible to display 8 characters after the found substring in those cases, since we are processing on a line-by-line basis. This is perfectly okay. If there are not 8 characters either before or after the found substring, just terminate the output report at that point.
7) Build up your solution in a modular fashion, debugging as you go. Do not attempt to write the whole program at once. If you feel lost at some point, simplify your problem down to something manageable. You might, for example, create a sample input file with a single sentence in it and see if your program can detect substrings within it. In any case, unless it is necessary to solve a problem, you should never have more than one function at once under development. Debug that function before moving on to the next. If you will code in this way, your overall development time will be much quicker.
8) Be alert to array overruns on either side as you look for substrings.
Deliverables
Please submit your C++ source code file. There is no output file on this problem.
input file:The Declaration of Independence of The United States of America
by Thomas Jefferson
Edition 1, (October 12, 2005)
THE DECLARATION OF INDEPENDENCE OF THE UNITED STATES OF AMERICA
IN CONGRESS, July 4, 1776
The unanimous Declaration of the thirteen united States of America
When in the Course of human events, it becomes necessary for one people to
dissolve the political bands which have connected them with another, and
to assume, among the Powers of the earth, the separate and equal station
to which the Laws of Nature and of Nature’s God entitle them, a decent
respect to the opinions of mankind requires that they should declare the
causes which impel them to the separation.
We hold these truths to be self-evident, that all men are created equal,
that they are endowed by their Creator with certain unalienable Rights,
that among these are Life, Liberty, and the pursuit of Happiness.—That to
secure these rights, Governments are instituted among Men, deriving their
just powers from the consent of the governed,—That whenever any Form of
Government becomes destructive of these ends, it is the Right of the
People to alter or to abolish it, and to institute new Government, laying
its foundation on such principles and organizing its powers in such form,
as to them shall seem most likely to effect their Safety and Happiness.
Prudence, indeed, will dictate that Governments long established should
not be changed for light and transient causes; and accordingly all
experience hath shown, that mankind are more disposed to suffer, while
evils are sufferable, than to right themselves by abolishing the forms to
which they are accustomed. But when a long train of abuses and
usurpations, pursuing invariably the same Object evinces a design to
reduce them under absolute Despotism, it is their right, it is their duty,
to throw off such Government, and to provide new Guards for their future
security.—Such has been the patient sufferance of these Colonies; and such
is now the necessity which constrains them to alter their former Systems
of Government. The history of the present King of Great Britain is a
history of repeated injuries and usurpations, all having in direct object
the establishment of an absolute Tyranny over these States. To prove this,
let Facts be submitted to a candid world.
He has refused his Assent to Laws, the most wholesome and necessary
for the public goooood.
He has forbidden his Governors to pass Laws of immediate and
pressing importance, unless suspended in their operation till his
Assent should be obtained; and when so suspended, he has utterly
neglected to attend to them.
He has r
efused to pass other Laws for the accommodation of large
districts of people, unless those people would relinquish the right
of Representation in the Legislature, a right inestimable to them
and formidable to tyrants only.
He has called together legislative bodies at places unusual,
uncomfortable, and distant from the depository of their Public
Records, for the sole purpose of fatiguing them into compliance with
his measures.
He has dissolved Representative Houses repeatedly, for opposing with
manly firmness his invasions on the rights of the people.
He has refused for a long time, after such dissolutions, to cause
others to be elected; whereby the Legislative Powers, incapable of
Annihilation, have returned to the People at large for their
exercise; the State remaining in the mean time exposed to all the
dangers of invasion from without, and convulsions within.
He has endeavoured to prevent the population of these States; for
that purpose obstructing the Laws of Naturalization of Foreigners;
refusing to pass others to encourage their migration hither, and
raising the conditions of new Appropriations of Lands.
He has obstructed the Administration of Justice, by refusing his
Assent to Laws for establishing Judiciary Powers.
He has made judges dependent on his Will alone, for the tenure of
their offices, and the amount and payment of their salaries.
He has erected a multitude of New Offices, and sent hither swarms of
Officers to harass our People, and eat out their substance.
He has kept among us, in times of peace, Standing Armies without the
Consent of our legislatures.
He has affected to render the Military independent of and superior
to the Civil Power.
He has combined with others to subject us to a jurisdiction foreign
to our constitution, and unacknowledged by our laws; giving his
Assent to their Acts of pretended legislation:
For quartering large bodies of armed troops among us:
For protecting them, by a mock Trial, from Punishment for any
Murders which they should commit on the Inhabitants of these States:
For cutting off our Trade with all parts of the world:
For imposing taxes on us without our Consent:
For depriving us, in many cases, of the benefits of Trial by Jury:
For transporting us beyond Seas to be tried for pretended offences:
For abolishing the free System of English Laws in a neighbouring
Province, establishing therein an Arbitrary government, and
enlarging its Boundaries so as to render it at once an example and
fit instrument for introducing the same absolute rule into these
Colonies:
For taking away our Charters, abolishing our most valuable Laws, and
altering fundamentally the Forms of our Governments:
For suspending our own Legislatures, and declaring themselves
invested with Power to legislate for us in all cases whatsoever.
He has abdicated Government here, by declaring us out of his
Protection and waging War against us.
He has plundered our seas, ravaged our Coasts, burnt our towns, and
destroyed the lives of our people.
He is at this time transporting large armies of foreign mercenaries
to compleat the works of death, desolation and tyranny, already
begun with circumstances of Cruelty & perfidy scarcely paralleled in
the most barbarous ages, and totally unworthy of the Head of a
civilized nation.
He has constrained our fellow Citizens taken Captive on the high
Seas to bear Arms against their Country, to become the executioners
of their friends and Brethren, or to fall themselves by their Hands.
He has excited domestic insurrections amongst us, and has
endeavoured to bring on the inhabitants of our frontiers, the
merciless Indian Savages, whose known rule of warfare, is an
undistinguished destruction of all ages, sexes and conditions.
In every stage of these Oppressions We have Petitioned for Redress in the
most humble terms: Our repeated Petitions have been answered only by
repeated injury. A Prince, whose character is thus marked by every act
which may define a Tyrant, is unfit to be the ruler of a free People.
Nor have We been wanting in attention to our Brittish brethren. We have
warned them from time to time of attempts by their legislature to extend
an unwarrantable jurisdiction over us. We have reminded them of the
circumstances of our emigration and settlement here. We have appealed to
their native justice and magnanimity, and we have conjured them by the
ties of our common kindred to disavow these usurpations, which would
inevitably interrupt our connections and correspondence. They too have
been deaf to the voice of justice and of consanguinity. We must,
therefore, acquiesce in the necessity, which denounces our Separation, and
hold them, as we hold the rest of mankind, Enemies in War, in Peace
Friends.
We, therefore, the Representatives of the United States of America, in
General Congress, Assembled, appealing to the Supreme Judge of the world
for the rectitude of our intentions, do, in the Name, and by the Authority
of the good People of these Colonies, solemnly publish and declare, That
these United Colonies are, and of Right ought to be Free and Independent
States; that they are Absolved from all Allegiance to the British Crown,
and that all polit
ical connection between them and the State of Great
Britain, is and ought to be totally dissolved; and that as Free and
Independent States, they have full Power to levy War, conclude Peace,
contract Alliances, establish Commerce, and to do all other Acts and
Things which Independent States may of right do. And for the support of
this Declaration, with a firm reliance on the Protection of Divine
Providence, we mutually pledge to each other our Lives, our Fortunes and
our sacred Honor.
Button Gwinnett
Lyman Hall
George Walton
William Hooper
Joseph Hewes
John Penn
Edward Rutledge
Thomas Heyward, Jr.
Thomas Lunch, Jr.
Arthur Middleton
John Hancock
Samuel Chase
William Paca
Thomas Stone
Charles Carroll of Carrollton
George Wythe
Richard Henry Lee
Thomas Jefferson
Benjamin Harrison
Thomas Nelson, Jr.
Francis Lightfoot Lee
Carter Braxton
Robert Morris
Benjamin Rush
Benjamin Franklin
John Morton
George Clymer
James Smith
George Taylor
James Wilson
George Ross
Caesar Rodney
George Read
Thomas McKean
William Floyd
Philip Livingston
Francis Lewis
Lewis Morris
Richard Stockton
John Witherspoon
Francis Hopkinson
John Hart
Abraham Clark
Josiah Bartlett
William Whipple
Samuel Adams
John Adams
Robert Treat Paine
Elbridge Gerry
Stephen Hopkins
William Ellery
Roger Sherman
Samuel Huntington
William Williams
Oliver Wolcott
Matthew Thornton