Pagini recente » Cod sursa (job #1086527) | Cod sursa (job #2122962) | Cod sursa (job #298696) | Cod sursa (job #2681974) | Cod sursa (job #2725303)
#include <fstream>
#include <sstream>
#include <vector>
#define maxRange 2000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,np, pi[maxRange], z[maxRange];
string a,b;
vector <int> v;
void zalgorithm()
{
int left = 0, right = 0;
for(int k = 1; k < n; k++)
{
if(k>right)
{
left = right = k;
while (right < n && b[right] == b[right - left])
{
right++;
}
z[k] = right - left;
right --;
}
else
{
int k1 = k - left;
if(z[k1] < right - k + 1)
{
z[k] = z[k1];
}
else
{
left = k;
while (right < n && b[right] == b[right - left])
{
right++;
}
z[k] = right - left;
right --;
}
}
}
}
/*
void prefix()
{
int k = 0;
pi[1] = 0;
for(int i = 2; i <= n; i++)
{
while(k && v[k+1] != v[i]) k = pi[k];
if(v[k+1] == v[i]) k++;
pi[i] = k;
}
}
*/
int main()
{
b = "";
f >> a;
np = a.length();
b += a + '$';
a = "";
f >> a;
b += a;
n = b.length();
zalgorithm();
for(int i = np+1; i < n; i++)
{
if (z[i] == np) v.push_back(i - (np + 1));
}
g << v.size() << '\n';
for(int i = 0; i < v.size() && i < 1000; i++)
{
g << v[i] << ' ';
}
return 0;
}