Pagini recente » Cod sursa (job #1661610) | Cod sursa (job #938803) | Cod sursa (job #2371598) | Cod sursa (job #2652215) | Cod sursa (job #2112855)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a,b;
vector<int> sol;
int urm[2000000];
int n,m;
void urma()
{
int k=-1;
urm[0]=0;
for(int x=1;x<m;x++)
{
while(k>0 && a[k+1]!=a[k]) k=urm[k];
if(a[k+1]==a[k]) k++;
urm[x]=k;
}
}
int main()
{
int x=-1;
f>>a;
f>>b;
n=b.length();
m=a.length();
// n=strlen(b);
// m=strlen(a);
urma();
for(int i=0;i<n;i++)
{
while(x>0&&a[x+1]!=b[i]) x=urm[x];
if(a[x+1]==b[i]) x++;
if(x==m-1)
{x=urm[m];
if(sol.size()<1000)
sol.push_back(i-m+1);
}
}
g<<sol.size()<<"\n";
for(int i=0;i<sol.size();i++)
g<<sol[i]<<" ";
return 0;
}