Pagini recente » Cod sursa (job #2425851) | Cod sursa (job #1153208) | Cod sursa (job #2326633) | Cod sursa (job #1573111) | Cod sursa (job #2430070)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char str[2000010],pattern[2000010];
int helper[2000010];
int found[2000010],indexFound;
int m,n;
void buildHelper()
{
for(int i = 1,j=0;i<=m;)
{
if(pattern[i]==pattern[j])
{
helper[i]=j+1;
i++;
j++;
}
else
{
if(j!=0)
j = helper[j-1];
else
i++;
}
}
}
void searchStr()
{
for(int i = 0,j = 0;i<=n;)
{
if(str[i]==pattern[j])
{
if(j==m)
found[indexFound++]=i-m;
j++,i++;
}
else
{
if(j!=0)
j = helper[j-1];
else
i++;
}
}
}
int main()
{
fin>>pattern>>str;
int i;
for(i = 0;pattern[i]!='\0';i++);
m = i-1;
for(i = 0;str[i]!='\0';i++);
n = i-1;
buildHelper();
searchStr();
cout<<indexFound<<endl;
if(indexFound>1000)
indexFound=1000;
for(int i = 0;i<indexFound;i++)
{
cout<<found[i]<<" ";
}
return 0;
}