Pagini recente » Cod sursa (job #3217646) | Cod sursa (job #2848096) | Cod sursa (job #2175835) | Cod sursa (job #985597) | Cod sursa (job #857165)
Cod sursa(job #857165)
#include <fstream>
#include <vector>
#include <cstring>
#define MAX 2000005
#define pb push_back
using namespace std;
char A[MAX], B[MAX];
int ap, aLgt, bLgt, Z[MAX];
vector<int> V;
int main()
{
ifstream in("strmatch.in"); in.getline(A, MAX); in.getline(B, MAX); in.close();
aLgt = strlen(A), bLgt = strlen(B);
for(int i = 1, R = 1; i < aLgt; i++)
{
Z[i] = min(max(0, R - i), Z[R - i]);
for(int j = i + Z[i]; A[Z[i]] == A[j] && j < aLgt; Z[i]++, j++);
if(i + Z[i] > R) R = i + Z[i];
}
for(int i = 0, R = 0, poz = 0; i < bLgt; i++)
{
poz = min(max(0, R - i), Z[R - i]);
for(int j = i + poz; B[j] == A[poz] && poz < aLgt; poz++, j++);
if(poz == aLgt)
{
ap++;
if(V.size() <= 1000) V.pb(i);
}
R = max(R, i + poz);
}
ofstream out("strmatch.out"); out<<ap<<"\n";
for(size_t i = 0; i < V.size(); i++) out<<V[i]<<" ";
out.close();
return 0;
}