Pagini recente » Cod sursa (job #1019596) | Cod sursa (job #2422646) | Cod sursa (job #1596526) | Cod sursa (job #2861900) | Cod sursa (job #2511061)
#include <iostream>
#include <fstream>
#include <string.h>
#define Nmax 3000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char pattern[Nmax],sir[Nmax];
int p[Nmax];
void READ()
{
fin>>pattern;
fin>>sir;
}
void pre_suf()
{
int j=0;
for(int i=1;i<strlen(pattern);++i)
{
if(pattern[i]==pattern[j])
{
p[i]=p[i-1]+1;
j++;
}
else{
while(pattern[i]!=pattern[j] && j!=0)
{
j=p[j-1];
}
if(pattern[i]==pattern[j])
{
p[i]=p[j]+1;
j++;
}
}
}
}
void solution()
{
int sol[Nmax];
int k=0;
int j=0;
for(int i=0;i<strlen(sir);++i)
{
if(j==(int)strlen(pattern))
{sol[++k]=i-j;
j=p[j-1];
}
if(sir[i]==pattern[j])
{
j++;
}
else if(j!=0){
while(sir[i]!=pattern[j] && j!=0)
j=p[j];
if(sir[i]==pattern[j])j++;
}
}
fout<<k<<"\n";
for(int i=1;i<=k;++i)
fout<<sol[i]<<" ";
}
int main()
{
READ();
pre_suf();
solution();
return 0;
}