Pagini recente » Cod sursa (job #2314074) | Istoria paginii runda/simulare_oji2020_31_10_2019/clasament | Cod sursa (job #1354707) | Cod sursa (job #1005172) | Cod sursa (job #2541997)
#include <bits/stdc++.h>
#include <set>
#include <queue>
using namespace std;
set<int> ListaVecini[1010];
set<int> Bolnavi;
set<int> Imbolnaviti;
set<int> Lista;
queue<int> ListaNoduri;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char t[2000000], p[2000000];
int k = -1, urm[2000000], contor;
int main(){
in.getline(p, 2000000);
in.getline(t, 2000000);
int m = strlen(p) - 1;
int n = strlen(t) - 1;
urm[0] = -1;
k = -1;
for(int i = 1; i <= m; i++){
while(k >= 0 && p[i] != p[k + 1])
k = urm[k];
if(p[k + 1] == p[i]) k++;
urm[i] = k;
}
k = -1;
for(int q = 0; q <= n; q++){
while(k >= 0 && p[k + 1] != t[q])
k = urm[k];
if(p[k + 1] == t[q]) k++;
if(k == m){
contor++;
Lista.insert(q - k);
}
}
out << contor << endl;
set<int>::iterator it;
for(it = Lista.begin(); it != Lista.end(); it++){
//cout << *it << " ->" << t + *it << endl;
out << *it << " ";
}
}