Pagini recente » Borderou de evaluare (job #633592) | Cod sursa (job #1322249)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
vector < pair<int,int> > sol;
int countSol=0;
void prefix(string A, vector <int> &fail)
{
int node=0;
fail[0]=fail[1]=0;
int m=A.size()-1;
for(int i=2;i<=m;i++)
{
while(A[node+1]!=A[i] && node!=0)
node=fail[node];
if(A[node+1]==A[i])
node++;
fail[i]=node;
}
}
vector <pair <int,int> > KMP (string A, string B)
{
vector <int> fail (A.size(),0);
prefix(A,fail);
int node=0,m=A.size()-1,n=B.size()-1;
for(int i=1;i<=n;i++)
{
while(A[node+1]!=B[i] && node!=0)
node=fail[node];
if(A[node+1]==B[i])
node++;
if(node==m)
{
countSol++;
node=fail[node];
if(countSol<=1000) sol.push_back(make_pair(i-m+1,i));
}
}
return sol;
}
#include <iostream>
int main()
{
string A,B;
f>>A;
f>>B;
A.insert(A.begin(),'x');
B.insert(B.begin(),'x');
sol=KMP(A,B);
g<<countSol<<'\n';
for(int i=0;i<sol.size();i++)
g<<sol[i].first-1<<' ';
}