Pagini recente » Cod sursa (job #108623) | Cod sursa (job #2043452) | Cod sursa (job #1410530) | Cod sursa (job #3272894) | Cod sursa (job #3004535)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int nmax = 2e6 + 2;
int N;
int z[2*nmax];
string concat,text,pattern;
vector<int> rasp;
inline void create_Z_array()
{
z[0] = 0;
int right = 0, left = 0;
for(int i=1; i < N; i++)
{
if(i > right)
{
right = left = i;
while(right < N && concat[right] == concat[right - left])
right ++;
z[i] = right - left;
right --;
}
else if(z[i - left] < right - i + 1)
{
z[i] = z[i - left];
}
else
{
left = i;
while(right < N && concat[right] == concat[right - left])
right ++;
z[i] = right - left;
right --;
}
}
}
int main()
{
fin>>pattern>>text;
concat = pattern + '$' + text;
N = concat.length();
create_Z_array();
for(int i=1; i < N; i++)
{
if(z[i] == pattern.length())
rasp.push_back(i - pattern.length() - 1);
}
int n = rasp.size();
fout<<n<<"\n";
for(int i=0; i < min(n,1000); i++)
{
fout<<rasp[i]<<" ";
}
return 0;
}