Pagini recente » Cod sursa (job #1199134) | Cod sursa (job #2409539) | Cod sursa (job #1233409) | Cod sursa (job #2564892) | Cod sursa (job #933359)
Cod sursa(job #933359)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define nmax 2000005
#define ll long long
string P, T;
int pi[nmax], rez[nmax];
void citeste(){
getline(f, P);
getline(f, T);
}
void prefix(){
pi[0] = -1;
for(int i=1, q=-1; i<P.size(); ++i){
while( q > -1 && P[q+1] != P[i]) q = pi[q];
if (P[q+1] == P[i]) q++;
pi[i] = q;
}
//pi[0] = 0;
}
void rezolva(){
prefix();
for(int i=0, q=-1; i<T.size(); ++i){
while( q > -1 && P[q+1] != T[i]) q = pi[q];
if (P[q+1] == T[i]) ++q;
if (q+1 == P.size() ){
rez[++rez[0]] = i-P.size() + 1;
}
}
g << rez[0] << "\n";
rez[0] = min(rez[0], 1000);
for(int i=1; i<=rez[0]; ++i){
g << rez[i] << " ";
}
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}