Pagini recente » Cod sursa (job #1768035) | Cod sursa (job #2238320) | Cod sursa (job #791718) | Cod sursa (job #2821745) | Cod sursa (job #1141645)
/** Z - algorithm **/
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int NMax = 2000010, MMax = 2000010;
int n, m, sol;
char A[NMax], B[MMax];
int Z[NMax];
int dp[MMax];
vector <int> ans;
// Z[i] = lungimea celui mai lung prefix al lui A care incepe pe pozitia i
// dp[i] = lungimea celui mai lung prefix al lui A care incepe in B pe pozitia i
void Read()
{
ifstream f("strmatch.in");
f>>(A + 1);
f>>(B + 1);
f.close();
}
void CreateZ()
{
n = strlen(A + 1);
m = strlen(B + 1);
Z[1] = 0;
for (int i = 2, j = 1; i<=n && A[i] == A[j]; ++i, ++j, ++Z[2]);
int maxim, position;
maxim = 2 + Z[2] - 1;
position = 2;
for (int i = 3; i <= n; ++i)
{
if (maxim < i)
{
int st, dr;
for (st = 1, dr = i; dr <= n && A[st] == A[dr]; ++st, ++dr, ++Z[i]);
maxim = i + Z[i] - 1;
position = i;
}
else
{
int iprim = i - position + 1;
if (i + Z[iprim] - 1 < maxim)
Z[i] = Z[iprim];
else
{
Z[i] = maxim - i + 1;
int st, dr;
for (st = maxim - i + 1 + 1, dr = maxim + 1; dr <= n && A[st] == A[dr]; ++st, ++dr, ++Z[i]);
maxim = i + Z[i] - 1;
position = i;
}
}
}
}
void CreateDP()
{
int maxim, position;
for (int i = 1; i<=m && A[i] == B[i]; ++i, ++dp[1]);
maxim = 1 + dp[1] - 1;
if (dp[1] == n)
{
++sol;
ans.push_back(1);
}
position = 1;
for (int i = 2; i <= m; ++i)
{
if (maxim < i)
{
int st, dr;
for (st = 1, dr = i; st <= n && dr <= m && A[st] == B[dr]; ++st, ++dr, ++dp[i]);
maxim = i + dp[i] - 1;
position = i;
if (dp[i] == n)
{
++sol;
if (ans.size() < 1000) ans.push_back(i);
}
}
else
{
int iprim = i - position + 1;
if (i + Z[iprim] - 1 < maxim)
dp[i] = Z[iprim];
else
{
dp[i] = maxim - i + 1;
int st, dr;
for (st = maxim - i + 1 + 1, dr = maxim + 1; st <= n && dr <= m && A[st] == B[dr]; ++st, ++dr, ++dp[i]);
maxim = i + dp[i] - 1;
position = i;
if (dp[i] == n)
{
++sol;
if (ans.size() < 1000) ans.push_back(i);
}
}
}
}
}
void Write()
{
ofstream g("strmatch.out");
g<<sol<<"\n";
for (vector <int> :: iterator it = ans.begin(); it != ans.end(); ++it)
g<<*it - 1<<" ";
g<<"\n";
g.close();
}
int main()
{
Read();
CreateZ();
CreateDP();
Write();
return 0;
}