Pagini recente » Cod sursa (job #3222118) | Cod sursa (job #413105) | Cod sursa (job #1541455) | Cod sursa (job #3238836) | Cod sursa (job #2481910)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
ifstream f("strmatch.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])
lps.push_back(1+(i++));
else
lps.push_back(lps[i]);
++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()-1,nr=0,k;
queue <int> q;
while(i<n)
{
if(b[i]==a[j])
if(j==m)
{
++nr,j=0,q.push(k),k=i;
if(nr==10000)
i=n;
}
else
++i,++j;
else
if(j==0)
++i,k=i;
else
j=lps[j];
}
g<<nr<<'\n';
while(!q.empty())
{
g<<q.front()<<' ';
q.pop();
}
return 0;
}