Pagini recente » Cod sursa (job #1314927) | Cod sursa (job #637444) | Cod sursa (job #1573233) | Cod sursa (job #530183) | Cod sursa (job #857175)
Cod sursa(job #857175)
#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 + 1, MAX); in.getline(B + 1, MAX); in.close();
aLgt = strlen(A + 1), bLgt = strlen(B + 1);
for(int i = 2, R = 1, index = 0, sw = 0; i <= aLgt; i++, sw = 0)
{
Z[i] = min(max(0, R - i + 1), Z[i - index + 1]);
for(int j = i + Z[i]; A[Z[i] + 1] == A[j] && j < aLgt; Z[i]++, j++, sw = 1);
if(i + Z[i] - 1 > R) R = i + Z[i] - 1, index = i;
}
for(int i = 1, R = 0, poz = 0, index = 0, sw = 0; i <= bLgt; i++, sw = 0)
{
poz = min(max(0, R - i + 1), Z[i - index + 1]);
for(int j = i + poz; B[j] == A[poz + 1] && poz < aLgt; poz++, j++, sw = 1);
//if(sw) poz--;
if(poz == aLgt)
{
ap++;
if(V.size() <= 1000) V.pb(i);
}
if(i + poz - 1 > R) R = i + poz - 1, index = i;
}
ofstream out("strmatch.out"); out<<ap<<"\n";
for(size_t i = 0; i < V.size(); i++) out<<V[i] - 1<<" ";
out.close();
return 0;
}