Pagini recente » Cod sursa (job #1860453) | Cod sursa (job #1704610) | Cod sursa (job #1090657) | Cod sursa (job #2381971) | Cod sursa (job #2541995)
#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++){
//out << *it << " ->" << t + *it << endl;
out << *it << " ";
}
}