Pagini recente » Cod sursa (job #2156129) | Cod sursa (job #949383) | Cod sursa (job #3136938) | Cod sursa (job #770486) | Cod sursa (job #1832023)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
//char sub[2000001],str[2000001];
string sub,str;
int pattern[2000001],n,m,rez[2000001];
int counter=0;
void makePattern()
{
for(int i=1,j=0;i<n;i++)
{
while(sub[i]!=sub[j] && j>0)
j=pattern[j-1];
if(sub[i]==sub[j])
pattern[i]=++j;
}
}
void searchPattern()
{
for(int i=0,j=0;i<m;i++)
{
while(str[i]!=sub[j] && j>0)
j=pattern[j-1];
if(str[i]==sub[j])
{
if(j==n-1)
{
rez[counter++]=i-n+1;
j=pattern[j];
}
else
j++;
}
}
}
int main()
{
fin >>sub>>str;
n=sub.length();//strlen(sub);
m=str.length();//strlen(str);
makePattern();
searchPattern();
// printf("%d\n",counter);
fout <<counter<<endl;
for(int i=0;i<counter && i<1000;i++)
// printf("%d ",rez[i]);
fout <<rez[i]<<" ";
return 0;
}