Pagini recente » Cod sursa (job #928472) | Cod sursa (job #3258132) | Cod sursa (job #2417446) | Cod sursa (job #1329562) | Cod sursa (job #2780175)
#include <iostream>
#include<cstring>
#include <list>
#include <stack>
#include<bits/stdc++.h>
#define nMax 1000
#define mMax 255
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int Urm[mMax];
char T[nMax], P[mMax];
int n,m;
void Next(char *P)
{
int k =-1,x;
Urm[0] = 0;
for(x=1;x<m;x++)
{
while(k>0 && P[k+1]!=P[x])
k = Urm[k];
if(P[k+1] == P[x])
k++;
Urm[k] = k;
}
}
int main()
{
int i,x=-1;
fin.getline(P,255);
fin.getline(T,1000);
n=strlen(T);
m=strlen(P);
vector<int>res;
Next(P);
for(i=0;i<n;i++)
{
while(x>0 && P[x+1]!=T[i])
x = Urm[x];
if(P[x+1] == T[i])
x++;
if(x == m-1)
{
res.push_back(i-m+1);
x = Urm[x];
}
}
fout<<res.size()<<'\n';
for(i=0;i<res.size();i++)
{
fout<<res[i]<<" ";
}
return 0;
}