Pagini recente » Cod sursa (job #1468690) | Cod sursa (job #2107820) | Cod sursa (job #1267207) | Cod sursa (job #2088471) | Cod sursa (job #1995497)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define nmax 2000001
char pattern[nmax],text[nmax];
int pref[nmax],n,m,k,pos,i,nr;
vector <int> sol;
void make_prefix()
{
int i;
for(i=2;i<=n;++i)
{
k=pref[i-1];
while(pattern[k+1]!=pattern[i] && k) k=pref[k];
if(pattern[k+1]==pattern[i]) ++k;
pref[i]=k;
}
}
int main()
{
fin>>pattern+1>>text+1;
n=strlen(pattern+1);
m=strlen(text+1);
make_prefix();
for(i=1;i<=m;++i)
{
while(pattern[pos+1]!=text[i] && pos) pos=pref[pos];
if(pattern[pos+1]==text[i]) ++pos;
if(pos==n) sol.emplace_back(i-pos+1);
}
fout<<sol.size()<<'\n';
for(auto x:sol)
{
fout<<x-1<<' ';
if(++nr==1000) break;
}
return 0;
}