Pagini recente » Cod sursa (job #2669397) | Cod sursa (job #363532) | Cod sursa (job #971384) | Cod sursa (job #1838401) | Cod sursa (job #1940849)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string N, M;
f>>N>>M;
N.insert(0, "!");
M.insert(0, "!");
unsigned int n = N.length() - 1;
unsigned int m = M.length() - 1;
int pi[n+1];
pi[1] = 0;
int k = 0;
for(unsigned int i = 2; i <= n; i++){
while(k > 0 && N[k+1] != N[i]){
k = pi[k];
}
if(N[k+1] == N[i]){
k++;
}
pi[i] = k;
}
// for(int i=1; i<= n; i++){
// g<<pi[i]<<" ";
// }
int q = 0;
int nr = 0;
vector<int> positions;
for(int i = 1; i <= m && nr < 1000; i++){
while(q > 0 && N[q+1] != M[i]){
q = pi[q];
}
if(N[q+1] == M[i]){
q++;
}
if(q == n){
nr++;
positions.push_back(i);
q = pi[q];
}
}
// g<<"n = "<<n<<'\n';
g<<nr<<'\n';
for(unsigned int i=0; i<nr; i++){
g<< (positions[i] - n) <<" ";
}
f.close();
g.close();
return 0;
}