Pagini recente » Cod sursa (job #26225) | Cod sursa (job #1819529) | Cod sursa (job #2533892) | Cod sursa (job #2533594) | Cod sursa (job #2481989)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
ifstream f("file.in");
ofstream g("strmatch.out");
void build_lps(string &s,vector <int> &lps)
{
lps.push_back(0);
int i=0,j=1,n=s.size();
while(j<n)
{
if(s[i]==s[j])
++i,lps.push_back(i),++j;
else
{
if(i!=0)
i=lps[i-1];
else
{
lps.push_back(0);
++j;
}
}
}
}
int main()
{
string a,b;
getline(f,a);
getline(f,b);
vector <int> lps;
build_lps(a,lps);
int i=0,j=0,n=b.size(),m=a.size(),nr=0,k;
queue <int> q;
while(i<n)
{
if(b[i]==a[j])
++i,++j;
if(j==m)
q.push(i-j),++nr;
if(i<n && b[i]!=a[j])
if(j)
j=lps[j-1];
else
++i;
}
cout<<nr<<'\n';
while(!q.empty())
{
cout<<q.front()<<' ';
q.pop();
}
return 0;
}