Pagini recente » Cod sursa (job #30212) | Cod sursa (job #465882) | Cod sursa (job #2784626) | Cod sursa (job #2544720) | Cod sursa (job #2760311)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string pattern,sir;
int lung,lungime;
int z[4000005];
vector<int>sol;
void Z_algorithm()
{
int L=0,R=0;
int n=lung;
for (int i = 1; i < n; i++)
{
if (i > R)
{
L = R = i;
while (R < n && pattern[R-L] == pattern[R]) R++;
z[i] = R-L;
R--;
}
else
{
int k = i-L;
if (z[k] < R-i+1) z[i] = z[k];
else
{
L = i;
while (R < n && pattern[R-L] == pattern[R]) R++;
z[i] = R-L;
R--;
}
}
}
for(int i=0;i<n;i++)
{
if( i>=lungime&&z[i]>=lungime )
{
sol.push_back(i-lungime);
}
}
}
int main()
{
f>>pattern;
f>>sir;
lungime=pattern.size();
pattern+=sir;
lung=pattern.size();
Z_algorithm();
g<<sol.size()<<'\n';
for(int i=0;i<sol.size()&&i<1000;i++) g<<sol[i]<<' ';
return 0;
}