Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- string text;
- int * LPS(const string & subStr) {
- int n = subStr.size();
- int * lps = new int[n];
- int j = 0;
- lps[0] = 0;
- int i = 1;
- while(i < n) {
- if(subStr[i] == subStr[j]) {
- j++;
- lps[i] = j;
- i++;
- }
- else {
- if(j == 0) {
- lps[i] = 0;
- i++;
- }
- else {
- j = lps[j - 1];
- }
- }
- }
- return lps;
- }
- int * reverseLPS(const string & subStr) {
- int n = subStr.size();
- int * lps = new int[n];
- int j = 0;
- // lps[0] = 0;
- //
- for(int i = n - 2; i >= 0; i--) {
- while(j > 0 and subStr[i] != subStr[n - j - 1]) {
- j = lps[n - j];
- }
- if(subStr[i] == subStr[n - j - 1]) {
- j++;
- }
- lps[i] = j;
- }
- for(int i = 0; i < n; i++) {
- cout << lps[i] << " ";
- }
- return lps;
- }
- int* findAllSubStr(const string & subStr) {
- int * lps = LPS(subStr);
- int n = subStr.size();
- int * res = new int[n];
- int r = 0;
- int i = 0, j = 0;
- while(i < (int) text.size()) {
- if(text[i] == subStr[j]) {
- i++;
- j++;
- if(j == n) {
- res[r++] = i - j;
- cout << i - j << endl;
- j = lps[j - 1];
- }
- }
- else {
- if(j != 0) {
- j = lps[j - 1];
- }
- else {
- i++;
- }
- }
- }
- int *res_array = new int[r];
- for(int i = 0; i < r; i++) {
- res_array[i] = res[i];
- }
- return res_array;
- }
- int findFirstSubStr(const string & subStr) {
- int * lps = LPS(subStr);
- int n = subStr.size();
- int i = 0, j = 0;
- while(i < (int) text.size()) {
- if(text[i] == subStr[j]) {
- i++;
- j++;
- if(j == n) {
- return i - j;
- }
- }
- else {
- if(j != 0) {
- j = lps[j - 1];
- }
- else {
- i++;
- }
- }
- }
- return -1;
- }
- int findLastSubStr(const string & subStr) {
- int * lps = reverseLPS(subStr);
- int n = subStr.size();
- int i = text.size() - 1, j = n - 1;
- while(i >= 0) {
- if(text[i] == subStr[j]) {
- i--;
- j--;
- if(j == 0) {
- return i;
- }
- }
- else {
- if(j != n - 1) {
- j = lps[n - j - 1];
- }
- else {
- i--;
- }
- }
- }
- return -1;
- }
- int main() {
- text = "ABABABCABABC";
- string pat = "abcabcy";
- int p = findLastSubStr(pat);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement