Pagini recente » Cod sursa (job #2825518) | winners29 | Cod sursa (job #274930) | Cod sursa (job #20652) | Cod sursa (job #1559530)
#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, S;
int z[nmax*2], rez[nmax];
void citeste(){
getline(f, P);
getline(f, T);
}
inline int compara(int x, int y){
int cnt = 0;
for(int i=x, j=y; j<(int)S.size(); ++i, ++j){
if(S[i] != S[j]) return cnt;
++cnt;
}
return cnt;
}
void bagaZvalues(){
S = P + T;
z[0] = S.size();
int L = -1; int R = -1;
for(int i=1; i<S.size(); ++i){
if (i > R){
z[i] = compara(0, i);
if (z[i] != 0){
L = i; R = i + z[i]- 1;
}
}else {
int lungA = R - L + 1; int lungB = R - i + 1;
int R2 = 0 + lungA - 1; int i2 = R2 - lungB + 1;
if (z[i2] < lungB){
z[i] = z[i2]; continue;
}
z[i] = lungB + compara(lungB+1, R+1);
if (i + z[i]-1 > R){
L = i; R = i + z[i] - 1;
}
}
}
}
void rezolva(){
bagaZvalues();
for(int i=P.size(); i<S.size(); ++i){
//cout << z[i] << " ";
if (z[i] >= P.size()){
rez[++rez[0]] = i - P.size();
}
}
g << rez[0] << "\n";
//cout << rez[0] << "\n";
rez[0] = min(rez[0], 1000);
for(int i=1; i<=rez[0]; ++i){
//cout << rez[i] << " ";
g << rez[i] << " ";
}
g << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}