Mai intai trebuie sa te autentifici.
Cod sursa(job #2367514)
Utilizator | Data | 5 martie 2019 11:11:28 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 28 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.04 kb |
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & -x)
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main() {
string needle, haystack;
in >> needle >> haystack;
haystack = " " + needle + haystack;
int sz = needle.size();
vector<int> kmp(haystack.size(), 0);
int k = 0, ans = 0;
vector<int> pos;
for(int i = 2; i < haystack.size(); i ++) {
while(k > 0 && haystack[k + 1] != haystack[i])
k = kmp[k];
if(haystack[k + 1] == haystack[i])
k ++;
kmp[i] = k;
if(kmp[i] >= sz ) {
if(pos.size() < 1000)
pos.push_back(i - 2 * sz);
ans ++;
}
}
out << ans << "\n";
for(auto it : pos)
out << it << " ";
return 0;
}