Pagini recente » Cod sursa (job #322523) | Cod sursa (job #472355) | Cod sursa (job #1235027) | Cod sursa (job #2753121) | Cod sursa (job #3178714)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char pattern[2000001],txt[2000001];
int dp[2000001],rez,n,m;
int poz[1001];
void search(int i, int j)
{
while(i<m)
{
if(txt[i]==pattern[j])
{
j++;
i++;
if(j==n)
{
rez++;
poz[rez]=i-n;
if(rez==1000)
return;
j=dp[n-1];
}
}
else
{
if(j==0)
i++;
else
j=dp[j-1];
}
}
}
int ps(int k, char c)
{
if(k==0)
{
if(pattern[0]==c)
return 1;
else
return 0;
}
else
if(pattern[k]==c)
return k+1;
else
return ps(dp[k-1],c);
}
int main()
{
cin>>pattern>>txt;
n=strlen(pattern);
m=strlen(txt);
int i;
for(i=1;i<n;i++)
{
dp[i]=ps(dp[i-1],pattern[i]);
}
search(0,0);
cout<<rez<<'\n';
for(i=1;i<=rez;i++)
cout<<poz[i]<<" ";
return 0;
}