Pagini recente » Cod sursa (job #2831470) | Cod sursa (job #1084484) | Cod sursa (job #1388387) | Cod sursa (job #1275862) | Cod sursa (job #3258591)
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int szmax = 2000000;
char s[szmax + 5];
char pat[szmax + 5];
int pr[szmax + 5];
int psz;
vector <int> sol;
void precompute()
{
int l = 0;
for(int i=2;pat[i];i++)
{
psz=i;
/// find last matching suffix
while(l!=0 && pat[i]!=pat[l+1])
l = pr[l];
/// advance pattern length
if(pat[i]==pat[l+1])
++l;
pr[i] = l;
}
}
int nrs;
int main(){
fin>>(pat+1);
fin>>(s+1);
precompute();
int l=0;
for(int i=1;s[i];i++){
while(l!=0 && s[i]!=pat[l+1])
l = pr[l];
if(s[i]==pat[l+1])
++l;
if(l==psz){
if(sol.size()<1000)
sol.push_back(i-psz);
nrs++;
l=pr[l];
}
}
fout<<nrs<<'\n';
for(auto& i : sol)
fout<<i<<' ';
}