Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <string>
- #include <vector>
- #include <stdlib.h>
- using namespace std;
- vector<int> prefixFunc(string s) {
- auto n = (int) s.length();
- vector<int> pi(n);
- for (int i=1; i<n; ++i) {
- int j = pi[i-1];
- while (j > 0 && s[i] != s[j])
- j = pi[j-1];
- if (s[i] == s[j]) ++j;
- pi[i] = j;
- }
- return pi;
- }
- vector<int> getSubstrings(const string &string1, const string &sub1) {
- int stringl = string1.length();
- int subl = sub1.length();
- vector<int> result;
- vector<int> borders = prefixFunc(sub1+"$"+string1);
- int count = 0;
- result.push_back(0);
- for (int i = 0; i < stringl; i++)
- {
- if (borders[subl + i + 1] == subl) {
- result.push_back(i-subl+1);
- count++;
- }
- }
- result[0] = count;
- return result;
- }
- int main()
- {
- string t;
- string p;
- vector<int> res;
- ifstream fin;
- fin.open("input.txt");
- if (fin.is_open())
- {
- getline(fin, t);
- getline(fin, p);
- fin.close();
- }
- res = getSubstrings(t, p);
- fstream fout;
- fout.open("output.txt", ios::out);
- fout << res.size() << "\n";
- for (std::vector<int>::const_iterator i = res.begin(); i != res.end(); ++i)
- fout << *i << "\n";
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement