Pagini recente » Cod sursa (job #662521) | Borderou de evaluare (job #1622027) | Monitorul de evaluare | Cod sursa (job #1519522) | Cod sursa (job #3325471)
#include <fstream>
#include <vector>
#include <cstring>
#define nmax (int)(2e6+1)
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int n,m,lps[nmax],sol;
string s,a;
vector<int>poz;
void precalculare(){
/// lps = longest prefix suffix
int i=1,len=0;
lps[0]=0;
while(i<n){
if(s[i]==s[len]){
len++;
lps[i++]=len;
}else if(len==0)
i++;
else
len=lps[len-1];
}
}
int main()
{
cin>>s>>a;
n=s.size(),m=a.size();
precalculare();
int i=0,j=0;
while(i<m){
if(a[i]==s[j]){
i++;
j++;
}else if(j!=0)
j=lps[j-1];
else
i++;/// daca j==0
if(j==n){
j=lps[j-1];
sol++;
poz.push_back(i-n);
}
}
cout<<poz.size()<<'\n';
for(int i=0;i<min(sol,1000);i++)
cout<<poz[i]<<" ";
return 0;
}