daily pastebin goal
53%
SHARE
TWEET

Untitled

a guest Feb 13th, 2018 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <vector>
  5. #include <stdlib.h>
  6.  
  7. using namespace std;
  8.  
  9. vector<int> prefixFunc(string s) {
  10.     auto n = (int) s.length();
  11.     vector<int> pi(n);
  12.     for (int i=1; i<n; ++i) {
  13.         int j = pi[i-1];
  14.         while (j > 0 && s[i] != s[j])
  15.             j = pi[j-1];
  16.         if (s[i] == s[j])  ++j;
  17.         pi[i] = j;
  18.     }
  19.     return pi;
  20. }
  21.  
  22.  
  23. vector<int> getSubstrings(const string &string1, const string &sub1) {
  24.     int stringl = string1.length();
  25.     int subl = sub1.length();
  26.     vector<int> result;
  27.     vector<int> borders = prefixFunc(sub1+"$"+string1);
  28.     int count = 0;
  29.     result.push_back(0);
  30.     for (int i = 0; i < stringl; i++)
  31.     {
  32.         if (borders[subl + i + 1] == subl) {
  33.             result.push_back(i-subl+1);
  34.             count++;
  35.         }
  36.     }
  37.     result[0] = count;
  38.  
  39.     return result;
  40. }
  41.  
  42. int main()
  43. {
  44.     string t;
  45.     string p;
  46.     vector<int> res;
  47.  
  48.     ifstream fin;
  49.     fin.open("input.txt");
  50.     if (fin.is_open())
  51.     {
  52.         getline(fin, t);
  53.         getline(fin, p);
  54.         fin.close();
  55.     }
  56.  
  57.     res = getSubstrings(t, p);
  58.  
  59.     fstream fout;
  60.     fout.open("output.txt", ios::out);
  61.     fout << res.size() << "\n";
  62.     for (std::vector<int>::const_iterator i = res.begin(); i != res.end(); ++i)
  63.         fout << *i << "\n";
  64.     fout.close();
  65.  
  66.     return 0;
  67. }
RAW Paste Data
Top