Pagini recente » Cod sursa (job #1912378) | Cod sursa (job #2633470) | Cod sursa (job #3179907) | Cod sursa (job #279654) | Cod sursa (job #790312)
Cod sursa(job #790312)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char p[2000000],t[2000000];
int urm[2000000];
vector<int> v;
int n,m;
void next(char* p)
{
int k=-1;
urm[0]=0;
for(int x=1;x<m;x++)
{
while( k>0 && p[k+1]!=p[x] )
{
k=urm[k];
}
if(p[k+1]==p[x])
k++;
urm[x] = k;
if(urm[x]==-1)
urm[x] = 0;
}
}
int main()
{
int x=-1;
fin.getline(p,2000000);
fin.getline(t,2000000);
n=strlen(t);
m=strlen(p);
next(p);
for(int i=0;i<n;i++)
{
while(x>0 && p[x+1]!=t[i])
x=urm[x];
if(p[x+1]==t[i])
x++;
if(x==m-1)
{
v.push_back(i-m+1);
x=urm[x];
}
}
fout<<v.size()<<'\n';
for(unsigned int i=0;i<v.size();i++)
fout<<v[i]<<' ';
fin.close();
fout.close();
return 0;
}