Pagini recente » Cod sursa (job #2850186) | Cod sursa (job #2914047) | Cod sursa (job #945157) | Cod sursa (job #3216665) | Cod sursa (job #2762398)
#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;
}